Talk:Knapsack problem

From Wikipedia, the free encyclopedia

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] 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.)