## [Algorithm 101] Unbounded Knapsack Problem

We started this problem with Project Euler #31 Coin Sums:

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

Unlike the 0-1 knapsack problem we discussed before, this time we get unlimited coins of each to sum up a certain number. Can we transform this problem into 0-1 knapsack problem?

The first thought may come up with: considering we can pick the ith item at most for $\left \lfloor W/value[i] \right \rfloor$ times, this problem is equivalent to 0-1 knapsack problem with $\left \lfloor W/value[i] \right \rfloor$ items which are the same with the original ith item to choose, and the transform formulation of f[w] will be:

$$f[w] = max\left \{ f[w], f[w - weight[i]] + value[i] \right \}$$

However, we don’t need go that far. Remember the solution of 0-1 knapsack problem? We used a reversed loop to keep the new-generated records won’t affect the calculated results(the new-generated ones are always larger), for each item we can pick once or not. But here we need to re-calculate the new-generated results, so we can just change the second reversed loop to a straight-forward loop, and here is our code for the problem above:

public class Solution {
public int coinSums(int N) {
int[] table = new int[N + 1], coins = new int[]{1, 2, 5, 10, 20, 50, 100, 200};
table[0] = 1;
for (int coin : coins) {
for (int i = coin; i < table.length; i++) {
table[i] += table[i - coin];
}
}
return table[N];
}

public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.coinSums(5));
System.out.println(solution.coinSums(10));
System.out.println(solution.coinSums(20));
System.out.println(solution.coinSums(200));
}
}