Talk:Knapsack problem/Bounded
Some technical details
Some solutions, including my perl one, use the 0-1 problem solution, but counting items with multiples as multiple different items. This is almost a good solution, but not quite: if some items have a huge count, the correct solution will not much care, but the hacked 0-1 solution generally can hang. Try for this example set the beer count to say 1000, and see how well your code copes. --Ledrug 09:11, 22 June 2011 (UTC)
- Hi, wp has the problem marked as taking wp:Pseudo-polynomial time. Does that mean that there is no better exact algo? --Paddy3118 16:34, 22 June 2011 (UTC)
- Using 0-1 solution is still Pseudo-polynomial time, but not all Pseudo-poly algorithms are equal. Suppose you have 1000 beer, each weighing 1, and your algorithm comes down to check on beers with 10 space to spare. The correct algorithm's decision tree branches 11 times, picking from 0 to 10 (weight capped), and see which gives best value. The 0-1 algorithm under the same sitution sees 1000 different items, each may be taken or not; because of the weight limit, it ends up trying taking any 10 of them, any 9 of them, etc, that is: Binomial(1000, 10) + Binomail(1000, 9) + ... the decision tree branches wildly, even though beer is beer, most of the different choices are really the same.