【算法】动态规划中01背包问题解析_01背包动态规划代码

📢博客主页：https://blog.csdn.net/2301_779549673
📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！
📢本文由 JohnKi 原创，首发于 CSDN🙉
📢未来很长，值得我们全力奔赴更美好的生活✨

文章目录

• 🏳️‍🌈一、01 背包问题概述
• 🏳️‍🌈二、问题分析与解法
• • ❤️（一）表示状态
  • 🧡（二）状态转移方程
  • 🧡（三）代码实现
• 🏳️‍🌈三、多种实现方式与优化
• • ❤️（一）暴力搜索
  • 🧡（二）记忆化搜索
  • 💛（三）动态规划
  • 💚（四）空间优化
• 🏳️‍🌈四、01背包例题
• • ❤️[DP42 【模板】完全背包](https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e?tpId=230&tqId=2032484&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196)
  • 🧡[416. 分割等和子集](https://leetcode.cn/problems/partition-equal-subset-sum/)
  • 💛[1049. 最后一块石头的重量 II](https://leetcode.cn/problems/last-stone-weight-ii/)
• 👥总结

🏳️‍🌈一、01 背包问题概述

01 背包问题是一个非常经典的动态规划问题，其场景设定为：给定一个背包，它有一定的容量限制，同时有若干种物品，每种物品都有对应的重量和价值，且每种物品只能选择放入背包一次（即选择 0 个或者 1 个），目标是在满足背包容量限制的条件下，求出能够装入背包的物品的最大价值总和。

这类问题最基本的解法就是利用二维数组动态规划。利用 f[i][j] 表示前i个物品中，在背包使用量为j ``时所能容纳的最大价值，最终结果在f[n][v]` 中。

具体情况可以分为两种，即不选择 i 位置的物品，结果为 f[i - 1][j] ，
以及选择 i 位置的物品，结果为 f[i][j - v[i]] + w[i]，当然这是有前提条件的，即当前背包容量的最大值比这个物品的体积大，不然会越界

🏳️‍🌈二、问题分析与解法

❤️（一）表示状态

我们通常会建立相应的数组来存储各个子问题的解。首先，用两个数组分别来表示物品的重量和价值，例如weight[n]表示 n 个物品各自的重量，value[n]表示 n 个物品各自的价值（这里 n 为物品的总数量）。
然后，定义动态规划的状态表示，一般会使用 dp[i][j]，它的含义是将前 i 件物品放入容量为 j 的背包里所能获得的最大价值。这里 i 的取值范围是从 0 到物品总数量，j 的取值范围是从 0 到背包的最大容量。

🧡（二）状态转移方程

对于dp[i][j]这个状态，需要考虑第 i 件物品的选择情况，主要分为两种：
不选第i 件物品：此时背包里的最大价值就等于前 i - 1 件物品放入容量为 j 的背包里的最大价值，即 dp[i][j] = dp[i - 1][j]。

选择第 i 件物品：前提是背包的容量 j 要大于等于第 i 件物品的重量 weight[i]，那么此时背包里的最大价值就是前 i - 1 件物品放入容量为 j - weight[i] 的背包里的最大价值，再加上第 i 件物品本身的价值 value[i]，即 dp[i][j] = dp[i - 1][j - weight[i]] + value[i]（前提满足容量条件）。

综合这两种情况，状态转移方程可以表示为：

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

🧡（三）代码实现

1. 未优化版代码
   以下是使用二维数组来实现的未优化的 01 背包问题代码示例：

#include #include using namespace std;int knapsack(vector<int>& weight, vector<int>& value, int capacity) {  int n = weight.size(); vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0)); for (int i = 1; i <= n; ++i) {  for (int j = 0; j <= capacity; ++j) {  dp[i][j] = dp[i - 1][j]; if (j >= weight[i - 1]) {  dp[i][j] = max(dp[i][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]); } } } return dp[n][capacity];}int main() {  vector<int> weight = { 2, 3, 4}; vector<int> value = { 3, 4, 5}; int capacity = 5; cout << \"背包能装的最大价值为: \" << knapsack(weight, value, capacity) << endl; return 0;}

在上述代码中：

• 首先定义了 dp 二维数组并初始化，外层循环遍历物品数量，内层循环遍历背包的不同容量情况。
• 在每次循环中，先默认不选当前物品，然后判断如果背包容量够放当前物品，就比较放和不放当前物品哪种情况能得到更大价值，更新 dp[i][j]的值。
• 最后返回将所有物品考虑完后，给定背包容量下能得到的最大价值。

2. 最终版代码（空间优化）
   我们可以发现，在计算 dp[i][j] 时，只用到了 dp[i - 1][...] 的值，所以可以将二维数组压缩成一维数组来优化空间复杂度。以下是优化后的代码示例：

#include #include using namespace std;int knapsack(vector<int>& weight, vector<int>& value, int capacity) {  int n = weight.size()