本文主要是介绍hdu 1114 Piggy-Bank (完全背包+背包放满)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最近在恶补背包，背包九讲写的真的是太牛了！！
现在的问题是给出存钱罐的容量，给出n种钱币的面值和重量
问你把存钱罐放满时对应钱币总和是多少？
若不可能输出impossible
现在我们把问题拆分开分析
1、先处理完全背包
dp[i][j]的含义是：前i个物品放在容积为j的背包所对应的最大值
完全背包的状态方程是：dp[i][j] = max{ dp[i-1][j], dp[i][j-v[i]]+w[i] }
注意这个形式和01背包的区别！！
01背包对应的是：dp[i][j] = max{ dp[i-1][j], dp[i-1][j-v[i]]+w[i] }
01背包成立的原因不再分析，这里只考虑完全背包和01背包的区别
完全背包每个硬币都有无数个这里dp[i][j]对应的是dp[i][j-v[i]]+w[i]是因为即使把第i个物品放进去，还可以放第i个物品，第i个物品并没有消失
再用滚动数组优化，要注意的是完全背包内层循环是从0到n；而01背包内层循环是从n到0；
（1）、01背包循环从n到0是因为dp[i][j]对应的是dp[i-1]中的值即当前行上一行的值（且列数在当前列或当前列的左边），因此如果内层循环从0到n，访问的只会是当前行的元素，无法访问上一行的元素
用下面这个图说明：
左侧对应的是完全背包循环从0到n,右侧对应的是01背包循环从n到0
理解的关键点在于，dp[i][j]对应的是上一行的元素还是当前行的元素
2、处理背包放满问题
背包九讲上说初始化dp[1...n]为-INF，dp[0]为0时背包的状态方程解决的是背包放满问题
这是为什么呢？
这样看：
if(j >= v[i])dp[j] = min(dp[j], dp[j-v[i]]+w[i]);输入一组v[i] w[i]后
内层j从0向n循环，发现初始j从0到v[i]仅当j==v[i]时才执行，其它情况下不执行因此j为其它值时dp仍为-INF
j从v[i]+1向后循环的过程中，仅当j为v[i]倍数时对应dp值才会改变，因此可以保证dp值改变当且仅当背包放满时
切结不能把下面代码中的INF置为真的int最大值，因为在循环中判断max时，对应INF可能会加上w[i]值，这时就会导致溢出从而变成负值
下面是该题的代码：
#include <map>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define esp 1e-9
#define MAXN 10010
#define ll long long
#define INF 99999999
#define BUG system("pause")
#define SW(a,b) a^=b;b^=a;a^=b;
using namespace std;
int w[MAXN];
int v[MAXN];
int dp[MAXN];
int main(void){int T;scanf("%d", &T);while(T--){int E, F;int n;scanf("%d%d", &E, &F);scanf("%d", &n);int sum = F-E;for(int i=0; i<n; ++i){scanf("%d%d", &w[i], &v[i]);}for(int i=1; i<=sum; ++i){dp[i] = INF;}
// for(int i=0; i<k; ++i){
// cout << wi[i] << "\t" << vi[i] << endl;
// }
// BUG;dp[0] = 0;for(int i=0; i<n; ++i){for(int j=0; j<=sum; ++j){if(j >= v[i])dp[j] = min(dp[j], dp[j-v[i]]+w[i]);cout << "dp[" << j << "] = " << dp[j] << endl;}}if(dp[sum] == INF) printf("This is impossible.\n");elseprintf("The minimum amount of money in the piggy-bank is %d.\n", dp[sum]);} return 0;
}
这篇关于hdu 1114 Piggy-Bank (完全背包+背包放满)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
