nyoj 硬币找零 995 （DP++技巧）

硬币找零

時間限制： 1000 ms  |           記憶體限制： 65535 KB 難度： 3

描述

在現實生活中，我們經常遇到硬币找零的問題，例如，在發工資時，财務人員就需要計 算最少的找零硬币數，以便他們能從銀行拿回最少的硬币數，并保證能用這些硬币發工資。 我們應該注意到，人民币的硬币系統是 100，50，20，10，5，2，1，0.5，0.2，0.1，0.05， 0.02，0.01 元，采用這些硬币我們可以對任何一個工資數用貪心算法求出其最少硬币數。 但不幸的是： 我們可能沒有這樣一種好的硬币系統， 是以用貪心算法不能求出最少的硬币數， 甚至有些金錢總數還不能用這些硬币找零。例如，如果硬币系統是 40，30，25 元，那麼 37 元就不能用這些硬币找零；95 元的最少找零硬币數是 3。又如，硬币系統是 10，7，5，1 元，那麼 12 元用貪心法得到的硬币數為 3，而最少硬币數是 2。 你的任務就是：對于任意的硬币系統和一個金錢數，請你程式設計求出最少的找零硬币數； 如果不能用這些硬币找零，請給出一種找零方法，使剩下的錢最少。

輸入

輸入資料：

第 1 行，為 N 和 T，其中 1≤N≤50 為硬币系統中不同硬币數；1≤T≤100000 為需要用硬币找零的總數。

第 2 行為 N 個數值不大于 65535 的正整數，它們是硬币系統中各硬币的面值。

當n，t同時為0時結束。

輸出

輸出資料：

如 T 能被硬币系統中的硬币找零，請輸出最少的找零硬币數。 

如 T 不能被硬币系統中的硬币找零，請輸出剩下錢數最少的找零方案中的最少硬币數。 

樣例輸入

4 12
10 7 5 1      

樣例輸出

2      

#include<stdio.h>
#include<string.h>
#define INF 0x3f3f3f3f
#include<algorithm>
using namespace std;
int dp[100010];
int main()
{
	int t,n,a;
	int i,j;
	while(scanf("%d%d",&n,&t),n|t)
	{
		for(i=1;i<=t;i++)
			dp[i]=INF;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a);
			for(j=a;j<=t;j++)
				dp[j]=min(dp[j],dp[j-a]+1);
		}
		for(i=t;dp[i]>=INF;i--);
			printf("%d\n",dp[i]);
	}
	return 0;
}