HDU 1114 Piggy-Bank(完全背包+恰好装满)

59 阅读 0 评论 39 点赞

我是靠谱客的博主飘逸香水，这篇文章主要介绍HDU 1114 Piggy-Bank(完全背包+恰好装满)，现在分享给大家，希望可以做个参考。

就以这道题来简单讲解一下完全背包问题，首先完全背包和01背包的区别在于01背包每样物品只有一个，用完了就不能再用了，而完全背包的物品是有无限个的，所以完全背包又衍生出能不能把背包恰好装满的问题。能否恰好装满问题对dp数组初始化的时候做点改变就行了。

下面是完全背包的核心代码：

复制代码

1
2
3
4
5
6

for(int i=0;i<p;i++){
for(int j=w[i];j<=Max;j++){
dp[j] = max(dp[j],dp[j-w[i]]+val[i]);
}
}

完全背包的核心代码和01背包也就只有一行不一样，完全背包的第二层的循环是顺序的，而01是倒序的，也正是这样才控制了物品是无限的还是只能用一次。

然后再说一下能否恰好装满这一问题，一般对于没有恰好装满这一要求我们需要对dp数组都初始化为0，因为这种问题只需要求出在不大于背包容量的情况下的最大或者最小价值，因为当dp[i]==0的时候相当于这个背包什么都没有装(相当于一个空背包)，是符合实际情况的。而要是要求判断是否能恰好装满，则需要将背包初始化为-∞，dp[i]==-∞表示这个背包还没有被定义(没有被用过)，因为当背包容量为0的时候背包里所装的价值也应该是0(啥都没装当然没价值啊)，所以需要把dp[0]初始化为0，而最后如果dp[m]为-∞的话，就说明这个背包没有被定义(装不满)，这就是根据题目要求，来对dp数组做的一个初始化。

下面是恰好装满的问题的核心代码：

复制代码

1
2
3
4
5
6
7
memset(dp,-INF,sizeof(dp));
dp[0] = 0;
for(int i=0;i<p;i++){
for(int j=w[i];j<=Max;j++){
dp[j] = max(dp[j],dp[j-w[i]]+val[i]);
}
}

下面是没有恰好装满要求的核心代码：

复制代码

1
2
3
4
5
6
7

memset(dp,0,sizeof(dp));
for(int i=0;i<p;i++){
for(int j=w[i];j<=Max;j++){
dp[j] = max(dp[j],dp[j-w[i]]+val[i]);
}
}

对于是否恰好装满，我们只需最后判断一下dp[Max]是否等于-INF就好了。

这道题就是一道完全背包的判断能否恰好装满的题，但这道题要求的是达到状态的最小价值，那么就把dp初始化为正无穷，然后每次存最小值就好了。

AC代码：

复制代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 500005;
const int INF = 0x3f3f3f3f;
// 初始化背包，因为要求最小值，需要初始化为最大值
int dp[MAXN];
int w[MAXN];
int val[MAXN];
int T,n,m;
int main()
{
cin>>T;
while(T--){
cin>>n>>m;
int p;
cin>>p;
int Max = m - n;
for(int i=0;i<p;i++){
cin>>val[i]>>w[i];
}
memset(dp,INF,sizeof(dp));
// 初始为INF表示为目前dp都没有被定义
dp[0] = 0;
// 因为当背包容量为0的时候能装的价值为0，这个状态应该定义一下
for(int i=0;i<p;i++){
for(int j=w[i];j<=Max;j++){
dp[j] = min(dp[j],dp[j-w[i]]+val[i]);
}
}
if(dp[Max]!=INF){
// 如果dp[Max]是INF说明没有被定义，说明达不到这种状态
cout<<"The minimum amount of money in the piggy-bank is "<<dp[Max]<<"."<<endl;
}
else{
cout<<"This is impossible."<<endl;
}
}
return 0;
}
/*
[来源] HDU 1114
[题目] Piggy-Bank
[大意]
完全背包模板题，还需要判断是否能恰好装满，题意是有一个小猪存钱罐，给你它空着时的重量，有给你装满硬币时候的重量，
两者相减就相当于背包容量了，然后给你n种硬币，然后分别给你价值和重量，要求把存钱罐装满，而且价值是最小的，最后判
断如果dp[Max]是个无效的值的话，就说明给的条件不能够把存钱罐装满。详细看代码吧。
[输入]
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.
*/

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 500005;
const int INF = 0x3f3f3f3f;
// 初始化背包，因为要求最小值，需要初始化为最大值
int dp[MAXN];
int w[MAXN];
int val[MAXN];
int T,n,m;
int main()
{
cin>>T;
while(T--){
cin>>n>>m;
int p;
cin>>p;
int Max = m - n;
for(int i=0;i<p;i++){
cin>>val[i]>>w[i];
}
memset(dp,INF,sizeof(dp));
// 初始为INF表示为目前dp都没有被定义
dp[0] = 0;
// 因为当背包容量为0的时候能装的价值为0，这个状态应该定义一下
for(int i=0;i<p;i++){
for(int j=w[i];j<=Max;j++){
dp[j] = min(dp[j],dp[j-w[i]]+val[i]);
}
}
if(dp[Max]!=INF){
// 如果dp[Max]是INF说明没有被定义，说明达不到这种状态
cout<<"The minimum amount of money in the piggy-bank is "<<dp[Max]<<"."<<endl;
}
else{
cout<<"This is impossible."<<endl;
}
}
return 0;
}
/*
[来源] HDU 1114
[题目] Piggy-Bank
[大意]
完全背包模板题，还需要判断是否能恰好装满，题意是有一个小猪存钱罐，给你它空着时的重量，有给你装满硬币时候的重量，
两者相减就相当于背包容量了，然后给你n种硬币，然后分别给你价值和重量，要求把存钱罐装满，而且价值是最小的，最后判
断如果dp[Max]是个无效的值的话，就说明给的条件不能够把存钱罐装满。详细看代码吧。
[输入]
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.
*/