Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For a bunch of items with values $v_i$ and weights $w_i$, and with a total weight $W$ that our bag can carry, how do we achieve maximum total value without breaking the bag? Dantzig proposed that we consider the ratio $v_i/w_j$, and add items for which this ratio is largest until the bag fills up. But this is regarded as an approximate solution.

I have also been thinking about this problem. I came up with the same solution as Dantzig and even proved it for the $0-1$ problem. Of course, I was suspicious of my proof even before I knew the method had been proposed before (since it would imply that $P= NP$). I am even more suspicious now.

So put me out of my misery. Why doesn't it work?

share|improve this question
    
Well, how would you prove that this method is the best in a general setting? –  naslundx Mar 20 at 16:18

1 Answer 1

up vote 19 down vote accepted

It doesn't work because it doesn't work.

Say you have $W=10$ and there are three kinds of objects:

  1. Type $A$ has weight 9 and value 90.
  2. Type $B$ has weight 2 and value 19.
  3. Type $C$ has weight 1 and value 1.

If you look at $v/w$, type $A$ wins, so you take one type $A$ object and fill up the remaining space with one type $C$, for total value $91$.

But the optimal solution takes five type $B$ objects for total value $95$.

We might characterize the general difficulty as follows: A choice that seemed good early on ran into trouble later, because our early choice of $A$, optimal in the short term, forces us to take the very bad $C$ afterwards. The optimal solution takes many choices that seem suboptimal in the short run, but which work well together.

This is quite typical of NP-complete problems. They have many parts that interact in complicated ways, so that the effects of a particular choice in one part of the problem can't be localized, but have far-reaching implications for choices made elsewhere. Compare this with the prototypical NP-complete problem, CNF-SAT, where the parts are logical clauses containing several components each, but each component may appear in multiple clauses. Each choice about the value of one component of one clause may have far-reaching effects on the other clauses.

Or similarly, consider bin packing. Items that fit optimally into the first bin may turn out to be just what was needed to fill out the space in later bins, so that an optimal packing of the first bin may get a short-term win at the expense of the overall packing; an overall optimal solution may pack the first bin suboptimally in order to save certain special items for later on.

share|improve this answer
    
For the $0-1$ problem it seems to me that choosing $A$ is optimal. I guess I should try to find a counter example that does work in the $0-1$ case, though. –  Matthew Matic Mar 20 at 16:58
2  
@Matthew Is the $0-1$ case the case where you can take at most one of each item? If so, split type $B$ into types $B_1\ldots B_5$ each with weight 2 and value 19, or if you want them to be different, give $B_i$ weight $2-\epsilon_i$ and value $19+\epsilon_i$. –  MJD Mar 20 at 16:58
    
That's great. Thanks. I think I identified my faulty step. I think it gives the optimal solution if it exactly obtains the weight bound, and not otherwise. –  Matthew Matic Mar 20 at 17:35
1  
@MatthewMatic: If you're interested in implementing a knapsack solver, check out this post: codereview.stackexchange.com/questions/44421/… –  rookie Mar 20 at 18:00
2  
I don't think that's true either. In 0-1 case with W = 10 consider A with (weight 6, value 60), B and C both with (weight 5, value 49), and D,E,F,G all with (weight 1, value 1) your method chooses A (with v/w = 10) first, then B and C don't fit, and it then it chooses D, E, F, and G to meet the weight bound exactly, with total value 64; while the optimal solution is B+C with total value 98. –  Sumudu Fernando Mar 20 at 21:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.