If i want to find three distinct int a,b,and c such that there are submitted to the constraint a+b+c=1000, is this a problem for the knapsack algo? I thought of doing this the bruteforce way, but that would be foolish 'cuz there are way too many combination of 3 numbers below 1000.
Last edited by nimitzhunter; 01-27-2011 at 09:50 PM.
"All that we see or seem
Is but a dream within a dream." - Poe
Not really. The knapsack problem would be if you had a bunch of numbers and had to pick the one set of three out of them that added up to 100. If you have a free choice, then you just pick a and b and set c = 100-a-b.Originally Posted by nimitzhunter
Tabstop, you mean that if there are many solution exists, then the knapsack problem would allow me to pick the optimal one? It seems like I am left with bruteforcing the way out of this. Thanks for your replay, tabstop.
"All that we see or seem
Is but a dream within a dream." - Poe
I think you lack something in your problem description. There are many solutions to a+b+c=1000, and they're all extremely easy to find, but you didn't say anything about one solution being better than the others.
You mean that a, b and c are part of a set? Like, given the subset of numbers, find 3 numbers for which a+b+c=1000? If so; I don't think that's NP complete. But then again, then what does your solution have to do with brute forcing 1000 numbers?
Brute forcing 1000 items isn't a lot by the way. Nor is 1,000,000. Usually brute forcing 10M takes about one second, depending of course on the processor and difficulty on the algorithm, but that's the rule I used for myself in programming contests. Usually brute force was fine for les than 10M items.
But as I said, if your problem is to select three items from a set so that a+b+c=1000, I'm quite sure that's not NP complete, but I'm not going to take the time to share the algorithm if I'm not sure that is indeed the problem. Also, I'm not sure my algorithm would even work, didn't think enough about it yet.
Not even a little bit. The knapsack problem is this: you have items weighing 1, 4, 7, 11, 13, 19, 23, 29, 35, 41, 49, 53, 57, 65, 72, 76, 79, and 85 pounds. You can get 100 pounds of stuff in your knapsack. Pick numbers but only numbers out of the list that add up to 100.
The problem as you originally described it is a (pair of) for loop(s), and therefore isn't nearly grand enough to have a name.
Do these items have to add up to exactly 100, 1000 etc? Can we make a best fit? Is the list sorted from highest to lowest or vise versa?
See the knapsack problem description on wikipedia. You are confusion things, since this problem requires a value pair of items in which one value determines the "value" and the other the "weight", for what is called a single constrain problem. There's nothing lower than that.
What you have on your problem is a single value, not a pair of values. As tabstop mentioned all you need is a couple of for loops to solve it.
>> Do these items have to add up to exactly 100, 1000 etc?
No. Their weight must be as high as possible up until a limit, while their value must be as high as possible.
>> Can we make a best fit?
That's exactly what you want to achieve.
>> Is the list sorted from highest to lowest or vise versa?
Usually there's only one possible solution. Multiple solutions in which the same value is achieved is most probably a weakness on the problem description.
Last edited by Mario F.; 01-28-2011 at 10:03 AM.
Originally Posted by brewbuck:
Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.
Yeah, I made the problem harder than it should be.
"All that we see or seem
Is but a dream within a dream." - Poe
