Talk:List of knapsack problems

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)

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

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

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)

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

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)

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)

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)