Differences between revisions 5 and 6
 ⇤ ← Revision 5 as of 2007-07-12 06:21:25 → Size: 931 Editor: OlegKobchenko Comment: ← Revision 6 as of 2008-12-08 10:45:28 → ⇥ Size: 939 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 2: Line 2: || inline:knapsack2.png|| || {{attachment:knapsack2.png}}|| Line 10: Line 10: that [[latex(\$7 = a_1 2 + a_2 3\$)]]. that <>.

Here's a simple illustration of Coin Change Problem for two items, which can easily be represented in a two-dimensional coordinate system.

Given target sum, say 7, we need to determine coefficients for the two items, say 2 and 3, so that .

This can be done by fixing possible y coordinates (for 3) and determining corresponding x coordinates (for 2). Doing so we see that

• fixing earlier coordinates narrows down later choices
• not all earlier fixings can yield later possibilities

This is also related to Knapsack problem, which attains maximization bounded by a second set of coefficients.