-
写在前面
背包问题是动态规划里面很重要的一部分，彻底理解各种背包问题，对动态规划的后续学习有很大的帮助.
更全的背包问题，可参看《背包九讲》.
学会了0-1背包后，多重背包、完全背包就比较容易理解.
一.什么是“完全背包”？
有这样一个问题：
在你面前放着n种宝石，每种宝石重量为wi，价值为vi，数量无限；你有一个最多可以放m重量的背包。现在你想在不超重的情况下，是你带走的宝石价值最大，问最大价值是多少？
二.如何做？
我们来看一道题，链接.
题目意思：你有一个空间为W的背包，在你前面放着n种石头，每种石头的价值为vi，体积为wi，数量无限.问：将背包装满，至少需要多少价值的石头？
我们从第一种物品开始取，for(i=1 to n).
设：dp[j]表示前i种物品，取得重量为j的石头时，需要的石头的最小价值.初始时dp[0]=0,其他为无穷大.
那么：dp[j]=min(dp[j],dp[j-w[i]]+v[i]).
即：
for(int i=0; i<=m; ++i)
dp[i]=INF;
dp[0]=0;
for(int i=0; i<n; ++i)
{
for(int j=w[i]; j<=m; ++j)
{
if(dp[j]>dp[j-w[i]]+v[i])
dp[j]=dp[j-w[i]]+v[i];
}
}
dp[i]=INF;
dp[0]=0;
for(int i=0; i<n; ++i)
{
for(int j=w[i]; j<=m; ++j)
{
if(dp[j]>dp[j-w[i]]+v[i])
dp[j]=dp[j-w[i]]+v[i];
}
}
注意：这儿的内循环是顺序！而0-1背包的内循环是逆序.
为什么？
我们在做0-1背包，计算dp[i][j]的时候，需要用到前面的值，而这个值是前i-1个物品的值（相当于更新前i-1个物品的值）.
而在做完全背包，计算dp[j]时，我们需要更新的是当前状态，也就是前i个物品的值.(也就是说：用前i-1个的值和当前值比较，更新当前值).
代码：（跟着代码计算一遍即可理解）
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2013-10-29-10.19
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define max(a,b) (a>b?a:b)
using namespace std;
typedef long long(LL);
typedef unsigned long long(ULL);
const double eps(1e-8);
const int MAXN=510;
const int MAXM=10010;
const int INF=(int)1e9+7;
int dp[MAXM];
int w[MAXN],v[MAXN];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--)
{
int m,v1,v2;
cin>>v1>>v2;
m=v2-v1;
int n;
cin>>n;
for(int i=0;i<n;++i)
{
cin>>v[i]>>w[i];
}
for(int i=0;i<=m;++i)
dp[i]=INF;
dp[0]=0;
for(int i=0;i<n;++i)
{
for(int j=w[i];j<=m;++j)
{
if(dp[j]>dp[j-w[i]]+v[i])
dp[j]=dp[j-w[i]]+v[i];
}
}
if(dp[m]==INF)
cout<<"This is impossible."<<endl;
else
cout<<"The minimum amount of money in the piggy-bank is "<<dp[m]<<"."<<endl;
}
return 0;
}
/*
*/
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2013-10-29-10.19
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define max(a,b) (a>b?a:b)
using namespace std;
typedef long long(LL);
typedef unsigned long long(ULL);
const double eps(1e-8);
const int MAXN=510;
const int MAXM=10010;
const int INF=(int)1e9+7;
int dp[MAXM];
int w[MAXN],v[MAXN];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--)
{
int m,v1,v2;
cin>>v1>>v2;
m=v2-v1;
int n;
cin>>n;
for(int i=0;i<n;++i)
{
cin>>v[i]>>w[i];
}
for(int i=0;i<=m;++i)
dp[i]=INF;
dp[0]=0;
for(int i=0;i<n;++i)
{
for(int j=w[i];j<=m;++j)
{
if(dp[j]>dp[j-w[i]]+v[i])
dp[j]=dp[j-w[i]]+v[i];
}
}
if(dp[m]==INF)
cout<<"This is impossible."<<endl;
else
cout<<"The minimum amount of money in the piggy-bank is "<<dp[m]<<"."<<endl;
}
return 0;
}
/*
*/