Talk:List of knapsack problems

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Low	This article has been rated as Low-priority on the project's priority scale.

Lists

	This article is within the scope of WikiProject Lists, an attempt to structure and organize all list pages on Wikipedia. If you wish to help, please visit the project page, where you can join the project and/or contribute to the discussion.ListsWikipedia:WikiProject ListsTemplate:WikiProject ListsList articles
???	This article has not yet received a rating on the project's importance scale.

Currently, the notation isn't the same all the way through. I'll probably fix this tomorrow. It is my hope that the page on knapsack problem will eventually refer to this page, and only focus on the regular knapsack problem. Xelnaga diku 16:08, 3 May 2006 (UTC)[reply]

Fixed this. Some references are still needed for the more obscure problems. Xelnaga diku 20:21, 3 May 2006 (UTC)[reply]

NP-Complete 201.213.37.39 03:19, 11 July 2007 (UTC)[reply]

In "Accelerando" by Charles Stross he mentions the "Blind Knapsack" problem. Several Google searches have lead to research papers on pay sites. I think it might belong here, does anyone know what it is? How it differs from the standard Knapsack problem? Thanks -Synapse001 —Preceding unsigned comment added by Synapse001 (talk • contribs) 15:34, 15 June 2009 (UTC)[reply]

Read over this while studying for my LP course. The reference to the Cutting Stock Problem should not have the constraint 0 <= Xi <= n; Xi need only be a non-negative integer. --HopefullyHelpfulStudent 20:41, 24 April 2012 (EST) — Preceding unsigned comment added by 98.224.224.194 (talk)

Change making problem[edit]

When we get to the subset sum problem, we have profits and weights identical, but x is still bounded as 0 or 1. If we unbound x, and create an unbounded subset sum problem, I think we have the change making problem. Is that correct? If so, I can add a section for it. There was some history in 2009 about the bounded one not being the change making problem. goodeye (talk) 19:23, 18 November 2013 (UTC)[reply]

The change-making problem is to minimise

\sum _{j=1}^{n}x_{j}

subject to

\sum _{j=1}^{n}w_{j}x_{j}=W.

where w_j and x_j are all positive integers, w₁ = 1 and w_j < w_j+1 for 1 ≤ j ≤ n − 1. The w_j are the coin values and the x_j are the number of coins of each denomination. Gandalf61 (talk) 08:54, 19 November 2013 (UTC)[reply]

This is great, thanks. I think it's correct to say this is a version of the knapsack problems, and belongs in this page. I'll add it. Thanks, goodeye (talk) 18:47, 19 November 2013 (UTC)[reply]