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

Ne0inhk

— 5 min read
【算法】动态规划中01背包问题解析
📢博客主页：https://blog.ZEEKLOG.net/2301_779549673
📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！
📢本文由 JohnKi 原创，首发于 ZEEKLOG🙉
📢未来很长，值得我们全力奔赴更美好的生活✨

在这里插入图片描述

文章目录

🏳️‍🌈一、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<iostream>#include<vector>usingnamespace std;intknapsack(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];}intmain(){  vector<int> weight ={ 2,3,4}; vector<int> value ={ 3,4,5};int capacity =5; cout <<"背包能装的最大价值为: "<<knapsack(weight, value, capacity)<< endl;return0;}

在上述代码中：

  • 首先定义了 dp 二维数组并初始化，外层循环遍历物品数量，内层循环遍历背包的不同容量情况。
  • 在每次循环中，先默认不选当前物品，然后判断如果背包容量够放当前物品，就比较放和不放当前物品哪种情况能得到更大价值，更新 dp[i][j]的值。
  • 最后返回将所有物品考虑完后，给定背包容量下能得到的最大价值。
  1. 最终版代码（空间优化）
    我们可以发现，在计算 dp[i][j] 时，只用到了 dp[i - 1][...] 的值，所以可以将二维数组压缩成一维数组来优化空间复杂度。以下是优化后的代码示例：
#include<iostream>#include<vector>usingnamespace std;intknapsack(vector<int>& weight, vector<int>& value,int capacity){ int n = weight.size(); vector<int>dp(capacity +1,0);for
Could not load content