-
题目描述
-
在现实生活中，我们经常遇到硬币找零的问题，例如，在发工资时，财务人员就需要计 算最少的找零硬币数，以便他们能从银行拿回最少的硬币数，并保证能用这些硬币发工资。我们应该注意到，人民币的硬币系统是 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
题目思路
-
设dp[ i ] 为金钱数为 i 时，最少的找零硬币数。
-
dp[ j ] = min( dp[ j ] , dp[ j - a[ i ] ] + 1 );
题目代码
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#define INF 100002
using namespace std;
/*
每个元素都可以有无限个
完全背包问题
dp[i]表示i元的找零个数最少的情况
*/
int n, t, a[55], dp[100010];
int main(){
// freopen("input.txt","r",stdin);while(scanf("%d%d",&n, &t)!=EOF && n &&t){for(int i = 0; i <= t; i++) dp[i] = INF;dp[0] = 0;for(int i = 0; i < n; i++){scanf("%d", &a[i]); for(int j = a[i]; j <= t; j++){dp[j] = min(dp[j], dp[j-a[i]]+1);}}int x = t;while(dp[x] == INF){x--;}printf("%d\n",dp[x]);}return 0;
}