背包问题(补充中）

1.01背包

        有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

        第 i 件物品的体积是 v[i]，价值是 w[i]。

        求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

对于01背包问题，只有选或不选，所有选法的集合便是由选的情况和不选的情况组成的

以下为未优化二维做法

#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int n, m;
int w[N], v[N];
int f[N][N];	//f[i][j]代表【从前i个物品中选，且最大容量为j的要求下的最大价值】
int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> v[i] >> w[i];}for (int i = 1; i <= n; i++) {			//枚举n个物品for (int j = 1; j <= m; j++) {		//枚举m个体积if(j < v[i])f[i][j] = f[i - 1][j];//如果j的体积甚至不如第i个物品大//那么也没有决策的必要了，当前的最优解就是上一层的最优解if (j >= v[i]) f[i][j] = max(f[i-1][j], f[i - 1][j - v[i]] + w[i]);	//如果体积可以装的下第i个物品，那么要进行决策/*首先前者f[i][j]代表状态不变，即不选择第i个物品时的{最优解}f[i-1][j-v[i]]+w[i]代表的是，选择上第i个物品时的{最优解}，采用先去掉一个i，再加上一个i的价值的算法取max则是从二者中抉择出最优的{最优解}*///此处不能暴力的直接每一层都取最大价值（使用贪心算法），贪心算法只注重于当前的利益//无法保证背包的容量被充分利用，从而无法保证最终得到的结果是最优解//动态规划便是对全局的决策，得到最优解}}cout << f[n][m];return 0;
}

一下为优化后的一维做法

 f[i][j]可以变为f[j]?    题目仅要求最终的f[n][m]结果，故讨论选前多少个物品意义不大

如果在原代码上进行修改可以得到

if(j <v[i]) f[i][j] = f[i-1][j];||\/
if(j <v[i])     f[j] = f[j];
//为等式，故可以直接删除

所以可以直接从v[i]枚举到m

但对于j >= v[i]时，在二维做法上，每次第i层的取max都用到了第i-1层，即在二维枚举时，保持了f[i-1]在使用时是原始数据，是没有被更新过的，没有被污染的

如枚举一个体积为1的物品时 f[2][3] = max(f[1][3] , f[1][2] + w[2]); 这时的f[1][2],f[1][3]都是没有被更新过的

而如果一维枚举时，如果直接使用升序枚举，那么就会导致使用 f[j] 时 f[j] 已经是被污染过的

如枚举一个体积为1的物品时 f[3] = max(f[3] , f[2] + w[2]); 那么此时f[2]已经在之前的枚举时被更新过了，导致了现在进行决策时f[2]已经不是原始数据了

综上，一维列举时需要逆序进行，这样可以避免小体积被提前更新

#include<iostream>
using namespace std;
const int N = 1e3 + 10;int f[N];
int n, m;
int v[N], w[N];int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> v[i] >> w[i];}for (int i = 1; i <= n; i++) {for (int j = m; j >= v[i]; j--) {f[j] = max(f[j], f[j - v[i]] + w[i]);}}cout << f[m];return 0;
}

2.完全背包

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 v[i]，价值是 w[i] 。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

完全背包问题中的物品是没有选择多少的限制的，故我们可以把集合的组成划分成：选1,2,3...k个前i个物品。

用代码实现出来便是这样

#include<iostream>
using namespace std;
const int N = 1e3 + 10;int n, m;
int v[N], w[N];
int f[N][N];	//f[i][j]表示从前i种物品中选，体积不超过jint main() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> v[i] >> w[i];}for (int i = 1; i <= n; i++) {for (int j = 0; j <= m; j++) {for (int k = 0; k * v[i] <= j; k++) {	//枚举选择第i种物品的个数	//下面的转移方程可能难以理解，但其实真正写出来是：//f[i][j] = max(f[i-1][j-v[i]*k] +w[i]*k)  (k = 0,1,2...)f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);}}}cout << f[n][m];return 0;
}

那么此问题如何优化？ 

     f[i][j] = max(f[i-1][j] , f[i-1][j-v[i]] + w[i], f[i-1][j-2v[i]] + 2w[i] , f[i-1][j-3v[i]] + 3w[i], ......)

f[i][j-v[i]] = max(f[i-1][j-v[i]] , f[i-1][j-2v[i]]+w[i], f[i-1][j-3v[i]] +2w[i], ......)

 通过观察上面两式，可以得知f[i][j-v[i]]的每一项都比上面的每一项少了一个w[i]，故可得

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

根据如上推导，可得到新的优化后的代码：

#include<iostream>
using namespace std;
const int N = 1e3 + 10;int n, m;
int v[N], w[N];
int f[N][N];	//f[i][j]表示从前i种物品中选，体积不超过jint main() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> v[i] >> w[i];}for (int i = 1; i <= n; i++) {for (int j = 0; j <= m; j++) {if(j < v[i]) f[i][j] = f[i - 1][j];		//体积不够时，不决策if (j >= v[i]) f[i][j] = max(f[i-1][j], f[i][j - v[i]] + w[i]);	//体积足够时，进行决策，根据推得的状态转移方程}}cout << f[n][m];return 0;
}

这么看，是不是和01背包的方程十分相似？

完全背包也可以继续优化成一维，但是与01背包不同的是，枚举体积时不需要变为逆序

回顾如上状态转移方程，都是由第i层转移来的，而不是i-1层，也就是说其正序枚举也是和优化前的状态转移方程式相同的

优化后代码如下：

#include<iostream>
using namespace std;
const int N = 1e3 + 10;int n, m;
int v[N], w[N];
int f[N];	int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> v[i] >> w[i];}for (int i = 1; i <= n; i++) {for (int j = v[i]; j <= m; j++) {f[j] = max(f[j], f[j - v[i]] + w[i]);}}cout << f[m];return 0;
}

当然还可以让价值和体积不用数组存储，而是分散在每一步进行输入，此处不再给出 

3.多重背包