Coins (POJ 1742)

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

Here is the count the the th type of coin and is its face value.

This formular cost time which is not feasible. We have to optimize the formular. Obviously if is able to be achieved, then must be able to be achieved and at last we have is able to be achieved. So we have is able to be achieved. So every time we just need to check if can be achieved within the count of the th type of coins. So the time cost can be reduced to .

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