河南省实验中学OJ 练习题4:硬币找零 dp

缘起

原先学数据结构和算法的时候学dp的时候学过找零问题——就是用最少的钱币数目找零固定的钱数. 一直没找到oj进行提交. 所以这次找到了一个 河南省实验中学OJ 练习题4:硬币找零

分析

题目是中文的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
4:硬币找零
查看 提交 统计 提问

总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 131072kB

描述
在现实生活中，我们经常遇到硬币找零的问题，例如，在发工资时，财务人员就需要计算最少的找零硬币数，以便他们能从银行拿回最少的硬币数，并保证能用这些硬币发工资。我们应该注意到，人民币的硬币系统是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的正整数，它们是硬币系统中各硬币的面值。

输出
如T能被硬币系统中的硬币找零，请输出最少的找零硬币数。
如T不能被硬币系统中的硬币找零，请输出剩下钱数最少的找零方案中的最少硬币数。

样例输入
4 12
10 7 5 1

样例输出
2
提示
題目來源：動態規劃經典習題

其实就是裸的dp，因为每种钱币数目无限, 所以dp公式特别好写, 一发就ac掉了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL
#define MIN(a,b) ((a)>(b)?(b):(a))

int n,t,a[55], dp[100005]; // dp[i] 表示钱数为i的时候, 需要的硬币最少数量

int main() 
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n, &t);
	for (int i = 1; i<=n; i++)
	{
		scanf("%d", a+i);
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[0] = 0;
	for (int i = 1; i<=t; i++)
	{
		int ans = 0x3f3f3f3f; // dp[i]的最小值
		for (int j = 1; j<=n; j++) // n种硬币
		{
			if (i>=a[j])
			{
				dp[i] = MIN(dp[i], dp[i-a[j]]+1); // i的总价值一定是从i-某张钱币得来的
			}
		}
	}
	while(dp[t]>=0x3f3f3f3f)
	{
		t--;
	}
	printf("%d\n", dp[t]);
	return 0;
}

ac情况

影法师 Accepted 10 584kB 53ms 706 B G++ 刚刚