背包问题 ¶
约 2002 个字 275 行代码 预计阅读时间 11 分钟
Acknowledgement¶
01 背包 ¶
0-1 背包问题定义 & 基本实现 ¶
问题：
有个容量为V大小的背包，有很多不同重量weight[i](i=1..n)不同价值value[i](i=1..n)的物品，每种物品只有一个，想计算一下最多能放多少价值的货物。
DP 的关键也是难点是找到最优子结构和重叠子问题，进而找到状态转移方程，编码就相对容易些。最优子结构保证每个状态是最优的，重叠子问题也即 n 状态的求法和 n-1 状态的求法是一样的；DP 在实现上一般是根据状态转移方程自底向上的迭代求得最优解（也可以使用递归自顶向下求解
回到 0-1 背包，每个物体 i，对应着两种状态： - 放入 - 不放入背包
背包的最优解是在面对每个物体时选择能够最大化背包价值的状态。0-1 背包的状态转移方程为
f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] }
f(i,v)表示前 i 个物体面对容量为 v 时背包的最大价值，c[i]代表物体 i 的 cost( 即重量 )，w[i]代表物体 i 的价值；
如果第i个物体不放入背包，则背包的最大价值等于前i-1个物体面对容量v的最大价值；
如果第i个物体选择放入，则背包的最大价值等于前i-1个物体面对容量v-cost[i]的最大价值加上物体i的价值w[i]。
对于实现，一般采用一个二维数组（状态转移矩阵）dp[i][j]来记录各个子问题的最优状态，其中dp[i][j]表示前i个物体面对容量j背包的最大价值。
下面给出 0-1 背包的基本实现，时间复杂度为O(N*V)，空间复杂度也为O(N*V)，初始化的合法状态很重要，对于第一个物体即f[0][j]，如果容量 j 小于第一个物体（编号为 0）的重量，则背包的最大价值为 0，如果容量 j 大于第一个物体的重量，则背包最大价值便为该物体的价值。为了能单步验证每个状态的最优解，程序最后将状态转移矩阵的有效部分输出到了文件。
代码如下：
#include <iostream>
using namespace std;
/* 0-1背包 版本1
* Time Complexity O(N*V)
* Space Complexity O(N*V)
* 设 V <= 200 N <= 10
* 状态转移方程：f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] }
*/
int maxValue[11][201]; /* 前i个物体面对容量j的最大价值，即子问题最优解 */
int weight[11];
int value[11];
int V, N;
void main()
{
int i, j;
scanf("%d %d",&V, &N);
for(i = 0; i < N; ++i)
{
scanf("%d %d",&weight[i],&value[i]);
}
for(i = 0; i < N; ++i)
{
for(j = 0; j <= V; ++j) /* 容量为V 等号 */
{
if(i > 0)
{
maxValue[i][j] = maxValue[i-1][j];
if(j >= weight[i]) /* 等号 */
{
int tmp = maxValue[i-1][j-weight[i]] + value[i];
maxValue[i][j] = ( tmp > maxValue[i][j]) ? tmp : maxValue[i][j];
}
}else /* 数组第0行赋值 */
{
if(j >= weight[0])
maxValue[0][j] = value[0];
}
}
}
printf("%d",maxValue[N-1][V]);
/* 重定向输出结果到文件 */
freopen("C:\\dp.txt","w",stdout);
for(i = 0; i <= N; ++i)
{
for(j = 0; j <= V; ++j)
{
printf("%d ",maxValue[i][j]);
}
printf("\n");
}
}
测试用例：
10 3
3 4
4 6
5 7
0-1 背包使用滚动数组压缩空间 ¶
所谓滚动数组，目的在于优化空间，从上面的解法我们可以看到，状态转移矩阵使用的是一个 \(N\times V\) 的数组 在求解的过程中，我们可以发现，当前状态只与前一状态的解有关，那么之前存储的状态信息已经无用了，可以舍弃的，我们只需要空间存储当前的状态和前一状态，所以只需使用\(2\times V\)的空间，循环滚动使用，就可以达到跟\(N\times V\)一样的效果。这是一个非常大的空间优化。 代码如下，我们可以在每轮内循环结束后输出当前状态的解，与上面使用二维数组输出的状态转移矩阵对比，会发现是一样的效果，重定向输出到文本有助加深理解。
#include <iostream>
using namespace std;
/* 0-1背包 版本2
* Time Complexity O(N*V)
* Space Complexity O(2*V)
* 设 V <= 200 N <= 10
* 状态转移方程：f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] }
*/
int maxValue[2][201]; /* 前i个物体面对容量j的最大价值，即子问题最优解 */
int weight[11];
int value[11];
int V, N;
void main()
{
int i, j, k;
scanf("%d %d",&V, &N);
for(i = 0; i < N; ++i)
{
scanf("%d %d",&weight[i],&value[i]);
}
for(i = 0; i < N; ++i)
{
for(j = 0; j <= V; ++j) /* 容量为V 等号 */
{
if(i > 0)
{
k = i & 1; /* i%2 获得滚动数组当前索引 k */
maxValue[k][j] = maxValue[k^1][j];
if(j >= weight[i]) /* 等号 */
{
int tmp = maxValue[k^1][j-weight[i]] + value[i];
maxValue[k][j] = ( tmp > maxValue[k][j]) ? tmp : maxValue[k][j];
}
}else /* 数组第0行赋值 */
{
if(j >= weight[0])
maxValue[0][j] = value[0];
}
}
}
printf("%d",maxValue[k][V]);
/* 重定向输出结果到文件 */
freopen("C:\\dp.txt","w",stdout);
for(i = 0; i <= 1; ++i)
{
for(j = 0; j <= V; ++j)
{
printf("%d ",maxValue[i][j]);
}
printf("\n");
}
}
这种空间循环滚动使用的思想很有意思，类似的，大家熟悉的斐波那契数列，\(f(n) = f(n-1) + f(n-2)\)，如果要求解 \(f(1000)\)，是不需要申请 1000 个大小的数组的，使用滚动数组只需申请 3 个空间 \(f[3]\) 就可以完成任务。
0-1 背包使用一维数组 ¶
使用滚动数组将空间优化到了 \(2\times V\)，在背包九讲中提到了使用一维数组也可以达到同样的效果，个人认为这也是滚动思想的一种，由于使用一维数组解 01 背包会被多次用到，完全背包的一种优化实现方式也是使用一维数组，所以我们有必要理解这种方法。 如果只使用一维数组\(f[0\dots v]\) （\(v\) 从\(V\) 到\(0\)），我们要达到的效果是：第i次循环结束后\(f[v]\)中所表示的就是使用二维数组时的\(f[i][v]\)，即前i个物体面对容量v时的最大价值。
我们知道 \(f[v]\) 是由两个状态得来的，\(f[i-1][v]\) 和 \(f[i-1][v-c[i]]\)，使用一维数组时，当第 i 次循环之前时，\(f[v]\) 实际上就是 \(f[i-1][v]\)， 那么怎么得到第二个子问题的值呢？
事实上，如果在每次循环中我们以 \(v=v\dots 0\) 的顺序推 \(f[v]\) 时，就能保证 \(f[v-c[i]]\) 存储的是 \(f[i-1][v-c[i]]\) 的状态。状态转移方程为：
f(v) = max{ f(v), f(v-c[i])+w[i] } v = V...0;
我们可以与二维数组的状态转移方程对比一下
f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] }
正如我们上面所说，\(f[v-c[i]]\) 就相当于原来 \(f[i-1][v-c[i]]\) 的状态。如果将 \(v\) 的循环顺序由逆序改为顺序的话，就不是 01 背包了，就变成完全背包了，这个后面说。这里举一个例子理解为何顺序就不是 01 背包了
假设 有物体\(z\)容量2，价值\(v_z\)很大，背包容量为5，如果\(v\)的循环顺序不是逆序，那么外层循环跑到物体\(z\)时，内循环在\(v=2\)时，物体\(z\)被放入背包，当\(v=4\)时，寻求最大价值，物体\(z\)放入背包，\(f[4]=max{f[4],f[2]+v_z}\)，这里毫无疑问后者最大，那么此时\(f[2]+v_z\)中的\(f[2]\)已经装入了一次物体\(z\)，这样一来该物体被装入背包两次了就，不符合要求，如果逆序循环\(v\)，这一问题便解决了。
代码如下，为了加深理解，可以在内循环结束输出每一个状态的情况到文本中，会发现与使用二维数组时的状态转移矩阵都是一样一样的。
#include <iostream>
using namespace std;
/* 0-1背包 版本3
* Time Complexity O(N*V)
* Space Complexity O(V)
* 设 V <= 200 N <= 10
* 状态转移方程：v = V...0; f(v) = max{ f(v), f(v-c[i])+w[i] }
*/
int maxV[201]; /* 记录前i个物品中容量v时的最大价值 */
int weight[11];
int value[11];
int V, N;
void main()
{
int i, j;
scanf("%d %d",&V, &N);
for(i = 0; i < N; ++i)
{
scanf("%d %d",&weight[i],&value[i]);
}
/*
* 对于第i轮循环
* 求出了前i个物品中面对容量为v的最大价值
*/
for(i = 0; i < N; ++i)
{
/*
* 内循环实际上讲maxV[0...v]滚动覆盖前一轮的maxV[0...V]
* 可输出对照使用二维数组时的情况
* j从V至0逆序是防止有的物品放入背包多次
*/
for(j = V; j >= weight[i]; --j) /* weight > j 的物品不会影响状态f[0,weight[i-1]] */
{
int tmp = maxV[j-weight[i]]+value[i];
maxV[j] = (maxV[j] > tmp) ? maxV[j] : tmp;
}
}
printf("%d",maxV[V]);
}
可以看出，使用一维数组，代码非常简练。
0-1 背包恰好背满 ¶
在 01 背包中，有时问到“恰好装满背包”时的最大价值，与不要求装满背包的区别就是在初始化的时候，其实对于没有要求必须装满背包的情况下，初始化最大价值都为 0，是不存在非法状态的，所有的都是合法状态，因为可以什么都不装，这个解就是 0，但是如果要求恰好装满，则必须区别初始化，除了 \(f[0]=0\)，其他的 \(f[1\dots v]\) 均设为 \(-\infty\) 或者一个比较大的负数来表示该状态是非法的。 这样的初始化能够保证，如果子问题的状态是合法的（恰好装满），那么才能得到合法的状态；如果子问题状态是非法的，则当前问题的状态依然非法，即不存在恰好装满的情况。 代码如下：
#include <iostream>
using namespace std;
int maxV[201]; /* 记录前i个物品中容量v时的最大价值 */
int weight[11];
int value[11];
int V, N;
void main()
{
int i, j;
scanf("%d %d",&V, &N);
for(i = 0; i < N; ++i)
{
scanf("%d %d",&weight[i],&value[i]);
}
for(i = 1; i <= V; ++i) /* 初始化非法状态 */
{
maxV[i] = -100;
}
for(i = 0; i < N; ++i)
{
for(j = V; j >= weight[i]; --j)
{
int tmp = maxV[j-weight[i]]+value[i];
maxV[j] = (maxV[j] > tmp) ? maxV[j] : tmp;
}
}
}
0-1 背包输出最优方案 ¶
一般来讲，背包问题都是求一个最优值，但是如果要求输出得到这个最优值的方案，就可以根据状态转移方程往后推，由这一状态找到上一状态，依次向前推即可。 这样就可以有两种实现方式，一种是==直接根据状态转移矩阵向前推==，另一种就是==使用额外一个状态矩阵记录最优方案的路径==，道理都是一样的。 当然也可以使用一维数组，代码更为简练，这里不罗列，相关代码可以到这里下载。 代码如下：
#include <iostream>
using namespace std;
/* 0-1背包 输出最优方案 2 直接根据状态数组算
* Time Complexity O(N*V)
* Space Complexity O(N*V)
* 设 V <= 200 N <= 10
* 状态转移方程：f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] }
*/
int maxValue[11][201]; /* 记录子问题最优解 */
int weight[11];
int value[11];
int V, N;
void main()
{
int i, j;
scanf("%d %d",&V, &N);
for(i = 0; i < N; ++i)
{
scanf("%d %d",&weight[i],&value[i]);
}
for(i = 0; i < N; ++i)
{
for(j = 0; j <= V; ++j)
{
if(i > 0)
{
maxValue[i][j] = maxValue[i-1][j];
if(j >= weight[i])
{
int tmp = maxValue[i-1][j-weight[i]] + value[i];
maxValue[i][j] = ( tmp > maxValue[i][j]) ? tmp : maxValue[i][j];
}
}else
{
if(j >= weight[0])
maxValue[0][j] = value[0];
}
}
}
printf("%d\n",maxValue[N-1][V]);
i = N-1;
j = V;
while(i >= 0)
{
if(maxValue[i][j] == maxValue[i-1][j-weight[i]] + value[i])
{
printf("%d ",i);
j = j - weight[i];
}
--i;
}
}
01 背包是背包问题的基础，加深理解的最好方式就是动手写一下，然后对照最终的状态转移矩阵一一比对。
转载于 : https://www.cnblogs.com/tham/p/6827172.html
例题 ¶
采药
//Author:PhilFan;
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[105][1005];
int t,m,tm[1005],w[1005];
int main()
{
cin>>t>>m;
for(int i = 1; i <= m; i++){
scanf("%d %d",&tm[i],&w[i]);
}
for(int i = 1; i <= m; i++){
for(int j = 1; j<= t; j++){
if(j>=tm[i])
f[i][j]=max(f[i-1][j],f[i-1][j-tm[i]]+w[i]);
else f[i][j]=f[i-1][j];
}
}
cout<<f[m][t];
return 0;
}