当前位置:   article > 正文

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

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

最近专注于写了一些关于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]是通过上一状态来的,最后都能正确的更新最后的值。但对于很多其它问题,遍历顺序的不同就会影响结果,比如完全背包问题还有利用滚动数组优化本题,总的来说,对于遍历顺序,要考虑随着遍历进行,每个值是否会被准确的更新,是否只跟前一个数据有关。对于绝大多数问题,先遍历物品再遍历背包既好理解又正确。

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

  1. for(int i = 1; i < weight.size(); i++) { // 遍历物品
  2. for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
  3. if (j < weight[i]) dp[i][j] = dp[i - 1][j];
  4. else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
  5. }
  6. }

 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;
}

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

相关问题:

416. 分割等和子集 - 力扣(LeetCode)

1049. 最后一块石头的重量 II - 力扣(LeetCode)

494. 目标和 - 力扣(LeetCode)

474. 一和零 - 力扣(LeetCode)

这些问题我都会在后面写出心得体会

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/木道寻08/article/detail/846382?site
推荐阅读
相关标签
  

闽ICP备14008679号