动态规划-01背包问题心得_动态规划算法背包问题实验心得

作者：木道寻08 | 2024-07-18 15:22:17

踩

动态规划算法背包问题实验心得

最近专注于写了一些关于01背包的问题，总结了些规律和心得，分享一下

01背包问题介绍：

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

题目如下：

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

力扣中没有01问题的母体，可以去46. 携带研究材料（第六期模拟笔试） (kamacoder.com)卡码网上联系。

对于简单的背包问题可以使用暴力破解，对于每个物品我们有两种选择：取于不取，可以利用回溯取到所有可能的情况，时间复杂度为O(2^n)，复杂度是指数级别的，所以我们可以用动态规划来降低复杂度。

对于动态规划问题，我们采取五部曲策略：

1、确认dp数组以及下标的含义

2、确定递推公式

3、dp数组初始化

4、确定遍历顺序

5、举例推导dp数组

上面五步都很重要，每一步出现错误都会造成很严重的错误，在后面的例题中会逐一说明其重要性。

进入解题：

对于01背包问题，我们采取五步走

1、确认dp数组以及下标的含义

采用二维数组dp[i][j]，表示从0-i件商品中任意挑选装入容量为j的背包中，可以得到的最大价值。dp数组的定义十分重要，后面的解题思路都是根据dp数组的定义走的，要是代码写到后面弄混了就回过头来看下定义。

2、确定递推公式

对于dp[i][j]我们有两种选择：取或不取物品i，所以可以从两个方向推导到dp[i][j]

不取物品i：

不取物品i，价值就不变，即dp[i][j]=dp[i-1][j]

取物品i：

决定要取该商品，则相当于将背包容量为j的背包空出weight[i]的重量来放物品i，价值就相当于dp[i-1][j-weight[i]]+values[i]，则递推式为dp[i][j]=max(dp[i-1][j]，dp[i-1][j-weight[i]]+values[i])

3、dp数组初始化

由上面的递推式我们要用到i-1，所以对于dp[0][j]，dp[i][0]我们要进行初始化，对于后者，我们直到其含义为将0-i件物品放入容量为0的背包的价值最大值，很显然都放不进去，所以dp[i][0]=0。对于dp[0][j]，我们要关注第一件商品的质量是否超过了背包容量，若没超过，即weight[0]<w，dp[0][j]=values[0]，若超过了，dp[0][j]=0。我们在初始化dp数组时就可以将其都初始化为0，因为价值不会出现负值，我们就只需要对dp[0][j]进行考虑了。

4、确定遍历顺序

对于遍历顺序，先遍历物品还是先遍历背包都可以，因为dp[i][j]是通过上一状态来的，最后都能正确的更新最后的值。但对于很多其它问题，遍历顺序的不同就会影响结果，比如完全背包问题还有利用滚动数组优化本题，总的来说，对于遍历顺序，要考虑随着遍历进行，每个值是否会被准确的更新，是否只跟前一个数据有关。对于绝大多数问题，先遍历物品再遍历背包既好理解又正确。

这里采取先遍历物品再遍历背包：


for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; 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>
#include<algorithm>
using namespace std;

int SearchMv(vector<int>weight, vector<int>value, int square) {
   //return 1;
   /*vector<vector<int>>dp(weight.size(), vector<int>(square + 1, 0));
   for (int i = weight[0]; i <= square; i++) {
       dp[0][i] = value[0];
   }
   for (int i = 1; i < weight.size(); i++) {
       for (int j = 1; j <= square; j++) {
           if (weight[i] > j) {
               dp[i][j] = dp[i - 1][j];
           }
           else {
               dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
           }
       }
   }
   return dp[weight.size()-1][square];*/
   vector<int>dp(square + 1, 0);
   for (int i = 0; i < weight.size(); i++) {
       for (int j = square; j >= 1; j--) {
           if (j >= weight[i]) {
               dp[j] = max(dp[j], (dp[j - weight[i]] + value[i]));
           }
       }
   }
   return dp[square];
}

int main() {
   int m, n;
   cin >> m;
   cin >> n;
   vector<int>weight(m, 0);
   for (int i = 0; i < m; i++) {
       cin >> weight[i];
   }
   vector<int>values(m, 0);
   for (int i = 0; i < m; i++) {
       cin >> values[i];
   }
   int maxValue = SearchMv(weight, values, n);
   cout << maxValue << endl;
   system("pause");
   return 0;
}

这是母题，后面其衍生的问题我也会写出博客记录，希望可以对读者有一定的启发