01背包理论基础

背包问题分类

01背包

在聊01背包之前，需要理解什么时候使用回溯，什么时候使用动态规划。

如果问题有明确的决策概念，一步步决策产生，就满足决策树模型，通常可以使用回溯来解决。

在这个基础上，能否用上动态规划，还有一些判断的加分项和减分项。

• 问题包含最大（小）或最多（少）等最优化描述。
• 问题的状态能够使用一个列表、多维矩阵或树来表示，并且一个状态与其周围的状态存在递推关系。

相应地，也存在一些“减分项”。

• 问题的目标是找出所有可能的解决方案，而不是找出最优解。
• 问题描述中有明显的排列组合的特征，需要返回具体的多个方案。

01背包问题描述如下：

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

这道题的特征：物品要么选要么不选（决策树模型），价值总和最大（最优性描述）

很明显应该选用动态规划

将物品用表格展示出来：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

再加一个背包最大重量。

问背包能背的物品最大价值是多少？

这个全局最优问题有两个可变限制，背包最大容量，选择要背哪些物品。而单个物品的重量和价值都是确定的，我们无法改变。

弱化全局最优问题：

我们给定最大容量和物品范围，此时最大价值是多少？

定义dp[i][j] 表示在[1,i]这么多物品里面选择，能够放入容量为j 的背包里面的最大价值是多少。

有了这个定义再看是否满足最优子结构

最大价值有两种情况：

• 没放入物品 i ：那么如果背包容量不变，即使不考虑物品 i ，最大价值也不会变 dp[i][j]==dp[i-1][j]。
• 放入了物品 i ：那么意味着如果把物品 i 拿出来，此时背包重量： j - weight[i]，最大价值就是 dp[i-1][j-wight[i]]。那么dp[i - 1][j - weight[i]] + value[i]（物品i的价值），就是背包放物品i得到的最大价值

本题的最优子结构：最大价值 dp[i][j] 等于不放入物品 i 和放入物品i 两种方案中价值更大的那一个。由此可推导出状态转移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-wight[i]] + val[i]])

无后效性也满足：物品 i 考虑不考虑在背包中与前 i 个物品无关，不会影响该决策。即，决策时独立的--状态是独立的。

再进一步明确dp数组的含义。

即**dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少**。

动规五部曲

1、确定dp数组含义

即**dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少**。

2、递推公式

dp[i][j] = max(dp[i-1][j], dp[i-1][j-wight[i]] + val[i]])

3、初始化dp数组

看这个递推公式，可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。

dp[0][j] 即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。

当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

除此之外，dp[i][0] 都为0，因为容量0什么也放不下。

dp[0][j] 和 dp[i][0] 都已经初始化了，那么其他下标应该初始化多少呢？

其实从递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出dp[i][j] 是由左上方数值推导出来了，那么 其他下标初始为什么数值都可以，因为都会被覆盖。

vector<vectir<int>> dp(m + 1,vector<int>(n+1,0))
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

4、遍历顺序

从这个dp二维数组看，i，j 依赖于正上方和左上方，因此可以一层一层遍历，也就是先遍历物品。当然一列一列遍历，先遍历容量也是可以的。

for(int i = 1;i < m;i++){
    for(int j = 0;j <= n;j++){
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

5、举例打印dp数组

代码实现

#include <iostream>
#include <vector>
int main() {
  int n, bagweight;
  std::cin >> n >> bagweight;
  std::vector<int> weight(n, 0);
  std::vector<int> value(n, 0);
  for (int i = 0; i < n; i++) {
    std::cin >> weight[i];
  }
  for (int j = 0; j < n; j++) {
    std::cin >> value[j];
  }
  std::vector<std::vector<int>> dp(n, std::vector<int>(bagweight + 1, 0));
  for (int j = weight[0]; j < bagweight + 1; j++) {
    dp[0][j] = value[0];
  }
  for (int i = 1; i < n; i++) {
    for (int j = 1; j < bagweight + 1; j++) {
      if (j < weight[i])
        dp[i][j] = dp[i - 1][j];
      else {
        dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
      }
    }
  }
  // 输出小明能够携带的研究材料的最大价值
  std::cout << dp[n - 1][bagweight] << std::endl;
  return 0;
}