4 ms·
Does this actually answer the stated problem of "deciding the subset of items to pack"? Looking at the solution table I can see that there are two possible sol
by Domenic_S 12y ago
Does this actually answer the stated problem of "deciding the subset of items to pack"?
Looking at the solution table I can see that there are two possible solutions, and I can see a max value of 6. But I can't see how v[4,3] implies packing objects 1 and 3.
- deleted 12y ago[deleted]
- deleted 12y ago[deleted]
- platunit2 12y agoAuthor here -- great point! I've updated the problem statement to make it more clear :) In this case, the article is simply asking "what is the highest value that you can achieve" Thanks for the feedback! :)
- Retric 12y agoYou can read the chart backwards to get an answer. Check 2 vs 3 @4lb. That's constant so 3 is not in there. Check 1 vs 2 @4lb. It changes so ob2 is in there. Now 3 weighs 2lb so look at 4lb - 2lb(ob3) = 2lb max weight. Check 0 vs 1@2lb. That's increasing so object 1 is in there 2lb - 1lb (ob1) = 1lb max. Check 0 @1lb that's greater than zero so object 0 is also in there. Thus, the solution is objects 0,1,2 but not 3. PS: Note, this only finds one solution there might be several. You can quickly find them with this chart but it's somewhat more complex. You would be looking for places where the max value does not change from the previous row, but the max value in the same row - the object weight = the max value - the object value.