Coins (POJ 1742)

Given a series of coins with their face values and count, you are asked to return how many prices under $m$ can them sum to. Let $DP[i][j]$ denotes if price $j$ can be sumed up to with the first $i$ types of coins. At first we should short the coins according to their face value, then we can use the iteration formular:

$$DP[i][j]=\begin{cases} true & DP[i-1][j-k\times v_{i}],k\in[0,c_{i}]\\ false & otherwise \end{cases}$$

Here $c_i$ is the count the the $i$th type of coin and $v_i$ is its face value.

This formular cost $O(N^2)$ time which is not feasible. We have to optimize the formular. Obviously if $DP[i - 1][j - (k + 1)\cdot x]$ is able to be achieved, then $DP[i - 1][j - k\cdot x]$ must be able to be achieved and at last we have $DP[i - 1][j - x]$ is able to be achieved. So we have $DP[i][j - x]$ is able to be achieved. So every time we just need to check if $DP[i][j]$ can be achieved within the count of the $i$th type of coins. So the time cost can be reduced to $O(N)$.

import java.io.*;
import java.util.*;

class Coin implements Comparable<Coin>{
    int x;
    int y;
    public Coin(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public int compareTo(Coin that) {
        Coin a = this;
        Coin b = that;
        return ((a.x == b.x) ? a.y - b.y : a.x - b.x);
    }
}

public class Coins {
    private static void solve(Coin[] coins, int m) {
        int[] dp = new int[m + 1];
        Arrays.fill(dp, 2000);
        dp[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            Coin c = coins[i];
            for (int j = c.x; j <= m; j++) {
                dp[j] = Math.min(dp[j - c.x] + 1, dp[j]);
            }
            for (int j = 0; j <= m; j++) {
                if (dp[j] <= c.y) dp[j] = 0;
                else dp[j] = 2000;
            }
        }
        int count = 0;
        for (int i = 1; i <= m; i++) {
            if (dp[i] == 0) count++;
        }
        System.out.println(count);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (true) {
            int n = in.nextInt(), m = in.nextInt();
            if (n == 0 && m == 0) return;
            Coin[] coins = new Coin[n];
            for (int i = 0; i < n; i++) {
                coins[i] = new Coin(in.nextInt(), 0);
            }
            for (int i = 0; i < n; i++) {
                coins[i].y = in.nextInt();
            }
            Arrays.sort(coins);
            solve(coins, m);
        }
    }
}