AOJ2069 Greedy, Greedy.

AOJ Volume20

問題リンク Greedy, Greedy.

  • 概要

N種類(c1, ... ,cN)の価値を持つ硬貨がある。この硬貨の群に対して以下の2点を調べよ。
1. 任意の金額をこれらのコインで表せる
2. 任意の金額を表すのに必要な最小枚数が常に貪欲的に求まる
1 <= N <= 50
0 < c1 < ... < cN < 1000

  • 解法

適当な金額の範囲[1, R]について1, 2を調べます。
2については、[1, R]における最小必要数をDPで求め、それらの値が貪欲法で求まった値と常に等しいか調べることでチェックできます。
1については、2を調べる過程で表現することができない金額が現れるかどうかでチェックします。
肝心の範囲の終端Rについてですが、N枚の硬貨の価値の総和とすることで通すことができました。
※ちなみに本家の解説によると、このRは、1番目に大きい価値と2番目に大きい価値の和とすることで十分とのことです。なんでも、貪欲で最適ではなくなる最小の価値xは
x < cN+cN-1
という証明がこの世に存在するとか

  • ソース
import java.util.Arrays;
import java.util.Scanner;

//Greedy, Greedy.
public class AOJ2069 {

	int n, INF = 1<<29;
	int[] c;

	int f(int x){
		int res = 0, k = n-1;
		while(x>0&&k>=0){
			res += x/c[k];
			x%=c[k--];
		}
		return x==0?res:INF;
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		for(int T=1;;T++){
			n = sc.nextInt();
			if(n==0)break;
			c = new int[n];
			int s = 0;
			for(int i=0;i<n;i++){
				c[i]=sc.nextInt(); s+=c[i];
			}
			int[] dp = new int[s+1];
			Arrays.fill(dp, INF);
			dp[0] = 0;
			boolean f1 = true, f2 = true;
			for(int x=1;x<=s&&f1;x++){
				for(int i=0;i<n;i++){
					if(x-c[i]>=0)dp[x] = Math.min(dp[x], dp[x-c[i]]+1);
				}
				if(dp[x]==INF)f1 = false;
				if(dp[x]<f(x))f2 = false;
			}
			System.out.println("Case #"+T+": "+(!f1?"Cannot pay some amount":!f2?"Cannot use greedy algorithm":"OK"));
		}
	}

	public static void main(String[] args) {
		new AOJ2069().run();
	}
}