1.1 题目
有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 Ci ,得到的
价值是 Wi 。求解将哪些物品装入背包可使价值总和最大。
1.2 基本思路
这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。
用子问题定义状态:即 F [i, v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得
的最大价值。则其状态转移方程便是:
- F [i, v] = max{F [i − 1, v], F [i − 1, v − Ci ] + Wi }
这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。
所以有必要将它详细解释一下:“将前 i 件物品放入容量为 v 的背包中”这个子问题,若只考虑第 i 件物品的策略(放或不放),那么就可以转化为一个只和前 i − 1 件物品相关的问题。如果不放第 i 件物品,那么问题就转化为“前 i − 1 件物品放入容量为 v 的背包中”,价值为 F [i − 1, v] ;如果放第 i 件物品,那么问题就转化为“前 i − 1 件物品放入剩下的容量为 v − Ci 的背包中”,此时能获得的最大价值就是 F [i − 1, v − Ci ] 再加上通过放入第 i 件物品获得的价值 Wi 。
伪代码如下:
F [0, 0..V ] ← 0
for i ← 1 to N
for v ← C i to V
F [i, v] ← max{F [i − 1, v], F [i − 1, v − Ci ] + Wi }
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=0;j<=v;j++)//考虑有商品体积为0,但是有价值的情况
{
if(j-vom[i]>=0)
dp[i][j]=max(dp[i-1][j],dp[i-1][j-vom[i]]+val[i]);
else dp[i][j]=dp[i-1][j];
}
}
printf("%d\n",dp[n][v]);
1.3 优化空间复杂度
以上方法的时间和空间复杂度均为 O(V N ) ,其中时间复杂度应该已经不能再优化了,但空间复杂度却可以优化到 O(V ) 。
先考虑上面讲的基本思路如何实现,肯定是有一个主循环 i ← 1 . . . N ,每次算出来
二维数组 F [i, 0 . . . V ] 的所有值。那么,如果只用一个数组 F [0 . . . V ] ,能不能保证第 i
次循环结束后 F [v] 中表示的就是我们定义的状态 F [i, v] 呢? F [i, v] 是由 F [i − 1, v] 和
F [i − 1, v − Ci ] 两个子问题递推而来,能否保证在推 F [i, v] 时(也即在第 i 次主循环中
推 F [v] 时)能够取用 F [i − 1, v] 和 F [i − 1, v − Ci ] 的值呢?
事实上,这要求在每次主循环中我们以 v ← V . . . 0 的递减顺序计算 F [v] ,这样才
能保证计算 F [v] 时 F [v − Ci ] 保存的是状态 F [i − 1, v − Ci] 的值。
伪代码如下:
F [0..V ] ←0
for i ← 1 to N
for v ← V to C i
F [v] ← max{F [v], F [v − Ci ] + W i }
其中的 F [v] ← max{F [v], F [v − Ci ] + Wi } 一句,恰就对应于我们原来的转移方程,因
为现在的 F [v − Ci ] 就相当于原来的 F [i − 1, v − Ci ] 。如果将 v 的循环顺序从上面的逆
序改成顺序的话,那么则成了 F [i, v] 由 F [i, v − Ci ] 推导得到,与本题意不符。
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=v;j>=vom[i];j--)
{
dp[j]=max(dp[j],dp[j-vom[i]]+val[i]);
}
}
printf("%d\n",dp[v]);
1.4 初始化的细节问题
我们看到的求最优解的背包问题题目中,事实上有两种不太相同的问法。有的题目
要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背包装满。一种区别
这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法,要求恰好装满背包,那么在初始化时除了 F [0] 为 0 ,其它
F [1..V ] 均设为 −∞ ,这样就可以保证最终得到的 F [V ] 是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将 F [0..V ]
全部设为 0 。
这是为什么呢?可以这样理解:初始化的 F 数组事实上就是在没有任何物品可以放
入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为 0 的背包可以在什
么也不装且价值为 0 的情况下被“恰好装满”,其它容量的背包均没有合法的解,属于
未定义的状态,应该被赋值为 -∞ 了。如果背包并非必须被装满,那么任何容量的背包
都有一个合法解“什么都不装”,这个解的价值为 0 ,所以初始时状态的值也就全部为 0
了。
Bone Collector
不要求背包刚好装满时，dp[]全部初始化为0
#include <cstdio>
#include<algorithm>
#include<string.h>
//#include<iostream>
using namespace std;
int main()
{
int t;
int dp[1010],val[1010],vom[1010];
scanf("%d",&t);
while(t--)
{
int n,v;
scanf("%d%d",&n,&v);
for(int i=1;i<=n;i++)
{
scanf("%d",val+i);
}
for(int i=1;i<=n;i++)
{
scanf("%d",vom+i);
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=v;j>=vom[i];j--)
{
dp[j]=max(dp[j],dp[j-vom[i]]+val[i]);
}
}
printf("%d\n",dp[v]);
}
}
0 1背包要求完全装满，dp[1,2,...v]初始化为-∞，dp[0]=0;
如果dp[v]<0，则表示体积为v的背包恰好装满是无解的
#include <cstdio>
#include<algorithm>
#include<string.h>
//#include<iostream>
using namespace std;
int main()
{
int t;
int dp[1010],val[1010],vom[1010];
scanf("%d",&t);
while(t--)
{
int n,v;
scanf("%d%d",&n,&v);
for(int i=1;i<=n;i++)
{
scanf("%d",val+i);
}
for(int i=1;i<=n;i++)
{
scanf("%d",vom+i);
}
memset(dp,-0x3f3f3f3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=v;j>=vom[i];j--)
{
dp[j]=max(dp[j],dp[j-vom[i]]+val[i]);
}
}
for(int i=0;i<=v;i++)
printf("v=%d,val=%d\n",i,dp[i]);
if(dp[v]<0) printf("No solution!\n");
else printf("%d\n",dp[v]);
}
}
/*
input:
1
5 10
1 2 3 4 5
2 4 6 7 8
output:
v=0,val=0
v=1,val=-1044266559
v=2,val=1
v=3,val=-1044266558
v=4,val=2
v=5,val=-1044266557
v=6,val=3
v=7,val=4
v=8,val=5
v=9,val=5
v=10,val=6
6
*/
1.5 一个常数优化
ps:这段伪代码中的Ｗi指的是体积(花费)，而不是价值
倒推 F(v) 需求出F(v-vom(n)),往后推 F(v-vom(n)),需求出F(v-vom(n)-vom(n-1)) 继续往后推 则推到第i步 为v-sigma(vom[i...n])
这个优化对V比较大时效果显著
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1010;
const int VOM=1010;
int dp[VOM];
int val[MAXN];
int vom[MAXN];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,v,sumOfV=0;
scanf("%d%d",&n,&v);
for(int i=1;i<=n;i++)
{
scanf("%d",val+i);
}
vom[0]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",vom+i);
sumOfV+=vom[i];
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
sumOfV-=vom[i-1];
int tmp=max(v-sumOfV,vom[i]);
for(int j=v;j>=tmp;j--)
{
dp[j]=max(dp[j],dp[j-vom[i]]+val[i]);
}
}
printf("%d\n",dp[v]);
}
return 0;
}
