HOW - DP 动态规划系列（三）（含01背包问题）

通过几个算法的学习，理解和掌握动态规划来解决背包问题。

一、01背包问题

对于面试的话，掌握01背包和完全背包就够用了，最多可以再来一个多重背包。

如果这几种背包分不清，可以参考下图：

图片来源：代码随想录

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

举例：

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

背包最大重量为4，问背包能背的物品最大价值是多少？

最直接的暴力解法

每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是 O(2^n)，这里的n表示物品数量。

如下是使用回溯法解决0-1背包问题的JavaScript实现。该算法通过递归尝试所有可能的物品组合，以找到在不超过背包容量的情况下能够获得的最大价值。

有关回溯法更多内容可以阅读：WHAT - 回溯系列（一）

/*** 使用回溯法解决0-1背包问题* @param {number[]} weight - 物品的重量数组* @param {number[]} value - 物品的价值数组* @param {number} w - 背包的最大容量* @returns {number} - 背包能装入物品的最大价值*/
function knapsackBacktracking(weight, value, w) {const n = weight.length;let maxValue = 0;/*** 回溯函数* @param {number} index - 当前考虑的物品索引* @param {number} currentWeight - 当前背包中的总重量* @param {number} currentValue - 当前背包中的总价值*/function backtrack(index, currentWeight, currentValue) {console.log(index, currentWeight, currentValue)// 如果当前重量已经超过背包容量，剪枝if (currentWeight > w) {return;}// 如果已经考虑完所有物品，更新最大价值if (index === n) {maxValue = Math.max(maxValue, currentValue);return;}// 不选择当前物品backtrack(index + 1, currentWeight, currentValue);// 选择当前物品（前提是不超过背包容量）backtrack(index + 1, currentWeight + weight[index], currentValue + value[index]);}// 从第0个物品开始回溯backtrack(0, 0 ,0);return maxValue;
}// 示例用法
const weight = [2, 3, 4, 5];
const value = [3, 4, 5, 6];
const capacity = 5;const result = knapsackBacktracking(weight, value, capacity);
console.log(`背包能装入物品的最大价值为: ${result}`);

动态规划解法

暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！

流程：

1. 确定 dp 数组以及下标的含义
2. 确定递推公式
3. dp 数组如何初始化
4. 确定遍历顺序
5. 举例推导 dp 数组

function knapsackDP(weight, value, w) {const n = weight.length;const dp = Array(w + 1).fill(0);for (let i = 0; i < n; i++) {for (let j = w; j >= weight[i]; j--) {if (j >= weight[i]) {dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}}return dp[w];
}// 示例用法
const weight = [2, 3, 4, 5];
const value = [3, 4, 5, 6];
const capacity = 5;
const resultDP = knapsackDP(weight, value, capacity);
console.log(`背包能装入物品的最大价值为: ${resultDP}`); // 输出: 背包能装入物品的最大价值为: 7

动态规划方法的时间复杂度为O(n*w)，在处理大规模数据时效率更高。

二、完全背包

完全背包又是也是01背包稍作变化而来，即：完全背包的物品数量是无限的。