## [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 *i*_{th} 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 *i*_{th} item to choose, and the transform formulation of f[w] will be:

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)); } }