# Why is Dantzig's solution to the knapsack problem only approximate

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?

-
Well, how would you prove that this method is the best in a general setting? – naslundx Mar 20 '14 at 16:18

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.

-
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 '14 at 16:58
@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 '14 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 '14 at 17:35
@MatthewMatic: If you're interested in implementing a knapsack solver, check out this post: codereview.stackexchange.com/questions/44421/… – rookie Mar 20 '14 at 18:00
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 '14 at 21:07
The text passage discusses the knapsack problem, a well-known optimization problem, and specifically focuses on Dantzig's approximate solution method. It includes a detailed example to illustrate why Dantzig's method does not always yield the optimal solution.
single_question_with_answer

the passage contains a single mathematical question: "why is dantzig's solution to the knapsack problem only approximate?" the answer is provided through an example that demonstrates a scenario where dantzig's method fails to find the optimal solution.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Why is Dantzig's solution to the knapsack problem only approximate

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?

-
Well, how would you prove that this method is the best in a general setting? – naslundx Mar 20 '14 at 16:18

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.

-
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 '14 at 16:58
@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 '14 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 '14 at 17:35
@MatthewMatic: If you're interested in implementing a knapsack solver, check out this post: codereview.stackexchange.com/questions/44421/… – rookie Mar 20 '14 at 18:00
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 '14 at 21:07
user
The text passage discusses the knapsack problem, a well-known optimization problem, and specifically focuses on Dantzig's approximate solution method. It includes a detailed example to illustrate why Dantzig's method does not always yield the optimal solution.

TYPE: SINGLE_QUESTION_WITH_ANSWER

The passage contains a single mathematical question: "Why is Dantzig's solution to the knapsack problem only approximate?" The answer is provided through an example that demonstrates a scenario where Dantzig's method fails to find the optimal solution.