Anonymous user
Talk:Knapsack problem/0-1: Difference between revisions
→Problem setup doesn't highlight the use of the exponential algorithm: new section
(→Delete in favor of Knapsack problem/Bounded: Certain algorithms may be unique to this.) |
|||
| (One intermediate revision by one other user not shown) | |||
Line 14:
This task is a subset of [[Knapsack problem/Bounded]]. That is, any program that's a solution to Knapsack problem/Bounded is also a solution to Knapsack problem/0-1. So I recommend we delete this task as entirely redundant. If desired, we can add the sample problem given here to Knapsack problem/Bounded. Thoughts? —[[User:Underscore|Underscore]] ([[User talk:Underscore|Talk]]) 12:10, 16 February 2010 (UTC)
:Algorithms for the 0-1 problem might not apply to the bounded problem (Such as the excellent [[Knapsack problem/0-1#Dynamic programming solution]] that I am trying to figure out at the moment). --[[User:Paddy3118|Paddy3118]] 14:33, 16 February 2010 (UTC)
:Generaly you are perfectly right. My Java solution for bounded problem contains also the 0-1 problem. I traced back the bounded solution to the 0-1 solution. I separeted the items as they would be independent units. E.g. if we have two books I dissolved them two independent books, and I thought on them as two different items. After this dissolving I solved the problem as a 0-1 problem. So from this aspect I think it is very important to know how you can solve the 0-1 problem. So I do not accomodate with you that we must delete the 0-1 problem. --[[User:Pelci|Pelci]] 17:17, 16 February 2010 (UTC)
== Problem setup doesn't highlight the use of the exponential algorithm ==
with the way the problem is set up, if you choose the highest valued item less than what the knapsack can carry you get the correct answer. normally, if you do this you will miss the right answer, but here it works. I think a small change to the list of items will make it work better for portraying the idea behind the problem.
| |||