poj 1384 Piggy-Bank 完全背包

缘起

学习完全背包. poj 1384 Piggy-Bank

分析

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
一个存钱罐,给出空罐子的时候它的重量与存满硬币的时候的重量,然后给你钱币的种数以及每种钱币的价值与重量,然
后要你计算罐子装满硬币之后徐最少有多少钱

【输入】
多样例，第一行是样例数目
每个样例首先是1 <= E <= F <= 10000两个数字，分别表示空的罐子的重量和满的罐子的重量. 然后是一个正整数N（1 <= N <= 500）. 表示硬币的种类. 然后N行分别给出各个种类的硬币价值c和重量w

【输出】
每个样例输出一行，表示罐子最小的价值，如果办不到, 就输出不可能

【样例输入】
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4

【输出】
The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.

【限制】
Time limit 1000 ms
Memory limit 10000 kB

首先说一下完全背包问题是什么. 【1】中介绍了01背包问题. 里面说到了每个物品只能取或不取. 而完全背包和01背包问题的唯一区别就在于完全背包允许你每种物品随意取多少件.

再说说完全背包问题的算法. 和【1】中01背包问题的算法唯一的区别在于（dp的意义与【1】完全一样）

1
2
3
4
5
6
7
8
9
10
11
12
13
dp[v=0,...,V]=0
for(i=1,...,N)
{
	cpack(c[i],w[i]);
}

cpack(c,w)
{
	for(v=c,...,V) // 这是与01背包算法唯一的区别点——遍历的顺序变成了正向(01背包是倒向,即01背包中v是从V到c)
	{
		dp[v] = max(dp[v], dp[v-c]+w);
	}
}

为什么变了一个内层循环遍历的顺序就是完全背包了呢? 也就是可以任取多少件了呢? 很简单~ 你想想就知道了.

下面回到本题. 本题其实就是一个完全背包问题——把硬币的价值看成w, 把硬币的重量看成c，而V就是F-E

只不过这里是求最小价值. 而且还必须装满背包. 所以dp的含义变成

1
dp[i][j]=前i件物品恰好装满容量为j的背包下的最小价值. 0<=i<=N

则 dp[0][0] = 0, 而dp[0][j] = inf（因为根本办不到，参见【1】）

然后开始进行dp, 其中dp公式变成

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

好了，下面是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
41
42
43
44
45
46
47
48
49
50
51
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL

int dp[10005],n,V,e,f;

void cp(int c, int w) // 完全背包
{
	for (int i = c; i<=V; i++)
	{
		if (dp[i]>dp[i-c]+w)
		{
			dp[i] =dp[i-c]+w;
		}
	}
}

int main() 
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{ 
		scanf("%d%d", &e, &f);
		V = f-e;
		memset(dp, 0x3f, sizeof(dp));
		dp[0] = 0;
		scanf("%d", &n);
		while(n--)
		{
			int c,w;
			scanf("%d%d", &w, &c);
			cp(c,w);
		} // 进行n次完全背包
		if (dp[V]==0x3f3f3f3f)
		{
			puts("This is impossible.");
		}
		else
		{
			printf("The minimum amount of money in the piggy-bank is %d.\n", dp[V]);
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 47ms
Memory 124kB
Length 730
Lang C++
Submitted 2019-08-19 13:25:52
Shared
RemoteRunId 20766394

参考

【1】https://yfsyfs.github.io/2019/08/18/%E7%99%BE%E7%BB%83oj-2773-%E9%87%87%E8%8D%AF-01%E8%83%8C%E5%8C%85/