hustoj 1596 最少硬币问题 dp

缘起

日常水题 hustoj 1596 最少硬币问题

分析

题目是中文的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
题目描述
设有n 种不同面值的硬币，各硬币的面值存于数组T［1:n］中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins［1:n］中。对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。

输入
输入的第一行中只有1 个整数给出n的值,第2 行起每行2 个数，分别是T[j]和Coins[j]。最后1 行是要找的钱数m。

输出
程序运行结束时，将计算出的最少硬币数输出。问题无解时输出-1。

样例输入
3
1 3
2 3
5 3
18

样例输出
5

我只想说，此题的数据甚水~ 竟然他喵的还有用贪心过的~ 其实不是所有的钱币系统都可以用贪心的（因为未必满足拟阵条件）

此题将每个钱币视作物品，将Coins[i]枚钱币拆成Coins[i]件单独的物品，从而化作01背包. 令dp[i][j] 是前i件物品达到j价值的最少需要选择的物品数. 则显然有

1
dp[i][j] = min{dp[i-1][j], dp[i-1][j-w[i]]+1}

利用滚动数组即是

1
dp[j] = min{dp[j], dp[j-w[i]]+1},  w[i]<=j<=20005

而注意j价值是要达到的, 所以初始值应该是（即一件物品都不选）

1
dp[j]=+inf for j>0, dp[0]=0

于是不难写出入下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
//#include "stdafx.h"

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

int n, dp[20005];

int main() 
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	memset(dp, 0x3f, sizeof(dp));
	dp[0] = 0;
	scanf("%d", &n);
	int t,c,nn = n,m;
	while(n--)
	{
		scanf("%d%d", &t, &c);
		while(c--)
		{
			for (int v = 20004; v>=t; v--)
			{
				dp[v] = MIN(dp[v], dp[v-t]+1);
			}
		}
	}
	scanf("%d", &m);
	while(dp[m]>=0x3f3f3f3f) m--;
	printf("%d\n", dp[m]);
	return 0;
}

ac情况

1358907 yfsyfs 1596 正确100% 1156 1 C++/Edit 585 B 2019-08-19 21:00:17 leader