【初窥算法】动态规划之背包问题（二）

写在前面

学习本文前，请先学习以下内容：

【初窥算法】初识动态规划（Dynamic programming）

【初窥算法】动态规划之背包问题（一）

本文主要学习背包问题中的完全背包问题。

完全背包问题概述

🙋完全背包和0/1背包有什么区别呢？

相较于0/1背包，完全背包中的每个物品可以使用无数次；而在0/1背包中，每个物品只能使用一次。

首先来介绍一下二维dp数组解决完全背包问题。这里重点介绍前两步。

Step1：定义dp数组

dp[i][j] 表示前 i 件物品取任意个物品放入容量为 j 的背包中所能获得的最大价值。

Step2：找到递推公式

这里递推公式和0/1背包相似，均要考虑两种情况：

不放物品 i：不放物品 i 的状态为 dp[i-1][j]，此时 dp[i][j] 就是 dp[i - 1][j] 。
放物品 i：放物品 i 的前一个状态为 dp[i][j - weight[i]] ，此时 dp[i][j - weight[i]] + value[i] ，就是背包放物品i得到的最大价值。

与0/1背包不同的是，在放物品 i 情况下，完全背包问题中，背包里可以存放物品 i 的。

dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);

我们知道在一维 dp 数组解决背包问题中，0/1背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。

// 01背包  先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：

🙋为什么要使用正序遍历背包呢？

一维dp数组在遍历时，从每一个元素往前看，因为是正序遍历，所以前面的元素都被更新过了，看到的都是“上一层的元素”，相当于是二维dp数组当前层的元素，元素使用了多次，符合完全背包的要求。

遍历顺序总结：