PKU演習問メモ(7/8)

No.	問題名	問題の種類および解法	難易度
1276	Cash Machine	硬貨の組み合わせ・動的計画法	★★☆☆☆

1276 Cash Machine

問題概要

キャッシュディスペンサーにn種類の通貨が入っており、それぞれの金額はdk[i],枚数はdn[i]である。
与えられた金額cashに対して、キャッシュディスペンサーの中の通貨で支払える、cashを超えない最大の金額を求めよ。

cash≦100000,dk[i]≦1000,nk[i]≦1000,n≦10を満たす。

解法

動的計画法による。
通貨で作れる金額をok[]に入れておき、通貨の種類ごとに配列を更新する。
DPの向きを間違えると作れないはずの金額が作れてしまうことになるので注意する。

ソースコード

int cash,n,nk[10],dk[10];
bool ok[100001];

int main()
{
	while(cin>>cash>>n)
	{
		rep(i,n)cin>>nk[i]>>dk[i];
		
		fill_n(ok,cash+1,0); ok[0]=1;
		rep(i,n)
		{
			for(int k=cash;k>=0;k--)if(ok[k])
			for(int j=1;j<=nk[i]&&k+dk[i]*j<=cash;j++)ok[k+dk[i]*j]=1;
		}
		int ans=cash;
		for(;ans>0&&!ok[ans];ans--);
		cout<<ans<<endl;
	}
	
	return 0;
}