Talk:Knapsack problem

From Wikipedia, the free encyclopedia

This article is within the scope of the following WikiProjects:
This article has an assessment summary page.

Contents

[edit] How aboutfour color problme

Authors of this page, how about four-color problem, job-shop problem? I'm sure there are others, but those are the ones I've heard of. Job shop is the problem of scheduling random jobs of random size for maximum use of shop. Four color is how many colors are required for a map so no country borders on another with same color. Ortolan88

see Linear programming ... -- Tarquin 20:30 Jan 14, 2003 (UTC)

Seems that bin packing is also related, since it is also about efficiency.

P.S. I don't see the four-color problem as being related.

--MarkH

[edit] Dynamic algorithm is wrong

As stated you could reuse items, when you choose a new item on each iteration you then use you previous solution for the highest value you can for a cost equal to the iteration cost you are on minus the value of your item. The problem is what if that solution already uses the item you chose. Lonjers (talk) 01:43, 20 April 2008 (UTC)

Agreed. The current version looks like a solution for the 0-1 problem, which does not allow repetitions. For the unbounded problem the recursion should probably be
A(i, j) = max(A(i - 1, j), vi + A(i, j - ci)) if ci ≤ j.
Can anyone check this? 85.2.63.93 (talk) 08:18, 20 April 2008 (UTC)

[edit] Question regarding the given solution

What happens if C, the total sum, isn't an integer? Then, there is no way one can reach A(C). We can approximate C either by floor or ceil but we can't be sure that the solution will be the best one, since one of the values can be smaller then the difference between C and it's approximated value. Bravemuta 16:57, 14 July 2007 (UTC)


By the way, the 1/2 approximation solution given in this article is also wrong. Consider if you've got one item that almost fills the knapsack, with value 1. The other items have value slightly less than one, and small size. Then you would get only value 1, when you could pick a lot of the smaller items and get a better value. —Preceding unsigned comment added by 66.67.122.13 (talk) 23:01, 16 December 2007 (UTC)


You are right I think the 1/2 approximation algorithm given is wrong. The correct one is to order the items by the ratio of their value to cost and take them from greatest to least. There is also a ( 1- E)*opt polynomial algorithm. I will fix this soon. Lonjers (talk) 01:39, 20 April 2008 (UTC)

[edit] DP for 0-1 only?

The last paragraph uses the word "essentials" which is seems totally wrong - it doesn't make any sense to me (English first language, still amateur [but reasonably knowledgeable] computer scientist). Also, the main thing, is it just me or is the dynamic programming algorithm only for the 0-1 problem (neither this article nor Levitin03 say so explicitly, but as far as I can see...) --대조 | Talk 20:24, 15 December 2005 (UTC)

The DP algorithm will work for the unbounded variant of the knapsack problem just fine. In fact, the algorithm as stated on the page would need to be modified to determine a solution for the 0/1 problem. "Essentials" is defined in the opening lines of this article. It's an unusual word, but I assume there's some tradition of using it here. --Dantheox 06:29, 16 December 2005 (UTC)

[edit] Need graphic change

It would be great to get the main graphic changed so that the dollar signs are in the right places. (They should precede the numbers: "$1" is correct, "1$" is incorrect.) —The preceding unsigned comment was added by Pkirlin (talk • contribs).

Done. Isn't SVG great? —Keenan Pepper 07:43, 9 July 2007 (UTC)

[edit] Continuous knapsack problem

Continuous knapsack problem redirects here but is not mentioned (presumably, it was removed). If I recall correctly this is the variant that allows fractional parts of items to be placed in the knapsack, and has a trivial polynomial-time solution. This is an important variant if only to demonstrate how changes in the problem description can alter the solution's complexity. Dcoetzee 03:40, 5 February 2008 (UTC)

[edit] Isn't the given problem in coNP????

The decision version of the 0-1 knapsack problem, as given, seems to be a member of coNP, NOT NP as the article states.

To see this: consider that to decide if a given solution to the 0-1 knapsack problem optimizes \sum_{j=1}^n p_j x_j subject to \sum_{j=1}^n w_j x_j\leq c we only need a poly-size witness proving it *doesn't* (some other solution with a higher value subject to the constraints). If there were a poly-size witness proving it *was* a member, then the decision problem would be in NP. —Preceding unsigned comment added by Austinjp (talk • contribs) 13:34, 31 March 2008 (UTC)

According to the article, the decision problem form of the knapsack problem is the question "can a value of at least V be achieved without exceeding the cost C?" This is not the same as "is a given solution the optimal solution?". -- Jitse Niesen (talk) 14:58, 31 March 2008 (UTC)
I see. There is some ambiguity: I missed the one sentence blurb about the decision problem before the contents and assumed the statement of NP-completeness at the end of the definitions section was about a decision form of the optimization problems in that same section (which we seem to agree is no NP-complete). I will do what I can to fix the ambiguity, feel free to correct me where I fail. --Austin Parker (talk) 01:02, 1 April 2008 (UTC)
Much better, thanks. I assume you are sure that the decision form of the optimization problem is coNP-complete. This is probably something obvious, but I know almost no complexity theory.
By the way, welcome here. I hope that you're enjoying the place. -- Jitse Niesen (talk) 10:23, 1 April 2008 (UTC)
Please ignore the bit I struck through. It is completely obvious. -- Jitse Niesen (talk) 10:26, 1 April 2008 (UTC)
You're choosing the wrong decision problem version. As with most optimization problems, the standard decision version of the problem is to say, given a problem and a bound v, is there a solution with value at least v? Given an algorithm for solving this problem, finding the optimal solution can then be done by binary search. This is in fact in NP and NP-complete. The complexity of other versions of this problem are not discussed in the literature and generally aren't very important, so I've removed them. Besides that, it's odd to discuss the complexity of other decision versions of one specific optimization problem and none of the hundreds of others. Dcoetzee 08:37, 2 April 2008 (UTC)