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

Leave a Reply

Your email address will not be published. Required fields are marked *

*