TopCoder SRM 331 Div1 Medium Shopping

問題

n種類のコインがあり、それぞれの価値はvalues[i]である。
X以下の整数の値段を全ておつりなしで支払えるようにコインを持ちたい。

コインは最小で何枚持つ必要があるか、求めよ。

制約条件

n≦10
values[i]≦1000
X≦1000

方針

動的計画法による。
dp[i]を、金額i以下を全て支払えるようにするために必要なコインの枚数とする。
これを、コインの種類とiについてループをまわして更新していくようなDPにより答えが求まる。

i番目のコインを使うためには、values[i]-1以下の全ての整数が支払える状態でなければならない。
逆に、values[i]-1以下の全ての整数が支払えるとき、i番目のコインをn枚使うことで、
values[i]*n以下の全ての整数が支払えるようになる。

ソースコード

int dp[1001];

class Shopping {
	public:
	int minNumber(int X, vector <int> values) 
	{
		sort(all(values));
		int n=values.size();
		
		rep(i,1001)dp[i]=inf;
		dp[0]=0;
		
		rep(i,n)rep(j,1001)if(j>=values[i]-1&&dp[j]!=inf){
			for(int k=0;;k++){
				int nxt=j+k*values[i];
				dp[min(X,nxt)]=min(dp[min(X,nxt)],dp[j]+k);
				if(nxt>X)break;
			}
		}
		return dp[X]==inf?-1:dp[X];
	}
};