Today we review a few more coding questions.

We can compare the coin counting puzzle with the classical knapsack problem. The knapsack problem is defined this way:
A thief robbing a store finds n items.
The ith item is worth vi dollars and weighs wi pounds, where vi and wi are
integers. The thief wants to take as valuable a load as possible, but he can carry at
most W pounds in his knapsack, for some integer W . Which items should he take?
(We call this the 0-1 knapsack problem because for each item, the thief must either
take it or leave it behind; he cannot take a fractional amount of an item or take an
item more than once.)

If the thief removes an item j from this load, the remaining load must be the most valuable load, weighing at most W-wj that the thief can take from the n-1 original items excluding j .
Therefore the knapsack problem can be written as follows:
case 1: with weight wj, find the maximum weights among n-1 weights to fill a bag that can hold W-wj
case 2: without weight wj, find the maximum weights among n-1 weights to fill a bag that can hold W

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)

for j from 0 to W do:
     m[0, j] := 0

for i from 1 to n do:
     for j from 0 to W do:
         if w[i-1] > j then:
             m[i, j] := m[i-1, j]
         else:
             m[i, j] := max(m[i-1, j], m[i-1, j-w[i-1]] + v[i-1])



The knapsack and the coin change are similar because we have to select the fewest high denomination
coins to reach a sum

we substitute the capacity W with the sum  to reach, the number of distinct items as n, the number of weights as denominations and the values as 1 each. We find the minimum instead of the maximum value as count of coins.