C++ 01背包问题

C++ 01背包问题

---

问题简单描述

有Ｎ件物品和总容量为Ｗ的背包，每件物品只能使用一次。
设第ｉ件物品的价值为ｖ(i),第ｉ件物品的重量为 w(i)。

求解: 问应将哪些物品放入背包中，在不超过最大容量的情况下使得总价值最大？

---

算法1实现：

#include<algorithm>
#include<stdio.h>
#include<time.h>
#include<stdlib.h> 
using namespace std;
const int MAXL = 1e5;
int w[MAXL+1],v[MAXL+1],f[MAXL+1][MAXL+1]; 
clock_t start ,stop;
int main(){int N,W;scanf("%d %d",&N,&W);for(int i = 1;i <= N;i++){scanf("%d %d",&w[i],&v[i]);}start = clock();for(int i = 1; i <= N;i ++ ){for(int j = 1;j <= W;j ++ ){if (j < w[i]) f[i][j] = f[i-1][j];else f[i][j] = max(f[i-1][j],f[i-1][j-w[i]]+v[i]);}}stop = clock();printf("%d",f[N][W]);printf("\n遍历时间%fs",(double(stop - start))/CLOCKS_PER_SEC);return 0;
}

其为两种转移方式：
1.当前容量小于第 i 件物品的重量
2.当前容量大于第 i 件物品的重量，则选择使得价值最大的物品

运行结果截图：

算法2实现：

空间改善后的算法

#include<bits/stdc++.h>
using namespace std;
const int L = 1e5;
int v[L+1],w[L+1],f[L+1];
clock_t start ,stop;int main(){int N,W;scanf("%d %d",&N,&W);for(int i = 0; i < N ; i++)scanf("%d%d",&w[i],&v[i]);memset(f,0,sizeof(f));start = clock();for(int i = 0;i < N; i++){for(int j = V;j > 0; j--){if ( w[i] <= j )f[j] = max(f[j],f[j-w[i]]+v[i]);}}printf("%d",f[W]);stop = clock();printf("\n遍历时间%.4fs",(double(stop - start))/CLOCKS_PER_SEC);return 0;
}

运行结果截图：

---

核心代码详解：

首先需要理解状态转移公式：

f[j] = max(f[j],f[j-w[i]]+v[i]);

这里的ｆ数组代表的含义为当前价值，对于该数组，其下标代表的含义为当前容量。

max函数里两项为两种选择，我们就是需要找到最大价值情况的背包。
第一种选择为不取第ｉ件物品放入背包
第二种选择为取第ｉ件物品放入背包
对于第一种选择，当前的容量应该不变，当前的价值也不发生变化。
对于第二种选择，当前容量需要减少第ｉ件的重量以及当前价值需要增加相应的价值。
对于遍历，首先最外层循环即为遍历每件物品，选择其中一些物品放入背包；对于第二层循环即从当前背包的最大容量逐渐递减遍历，每次当前价值与上一次的价值进行比较，选择相应容量下的最大价值覆盖；对于该层的 if 语句只是边界条件，即当前背包容量必须大于等于需要放入的物品重量，防止溢出。

for(int i = 0;i < N;i++){for(int j = V;j > 0;j--){if (w[i] <= j )f[j] = max(f[j],f[j-w[i]]+v[i]);}}

最终输出的结果为：

printf("%d",f[V]);

为什么会是ｆ数组最后一个？
通过算法的迭代，此时它表示的容量就是Ｖ的最大价值。

---