博客

0-1背包问题简介

关于0-1背包问题，相信大家都不陌生，这是一个典型的动态规划问题，但是平时上课对这些的理解可能会不太够，我也是如此，所以参考了一些资料，对0-1背包问题做了一个简单的总结。还是那句话

本人很菜，不喜勿喷，谢谢！

0-1背包问题其实就是这么个情况：我有一个限制重量的背包，然后有一些有价值且有重量的物品，我要往里面装物品，现在需要找一个方案，使我的背包尽可能地装满，并且价值最高。

思路简介

首先，我们简单考虑一下贪心算法，既然是贪心，就必须找到局部的最优子结构，那么，什么是局部最优子结构呢？ 答案应该是找单位价值最大的物品往里面装，但是，可以发现，装到最后，背包里所装物品可能不是最优解。

以背包容量为4，物品重量分别为1,3,4,对应的价值为8,20,30为例。

第一次的局部最优解肯定是装重量为1、价值为8的物品；

第二次由于背包容量问题，我只能装重量为3、价值为20的物品，那么，此时的背包总价值为28，显然会有一个30的更优解。

所以，贪心算法肯定不行，但是动态规划是可以的，网上有很多讲解动态规划的大佬，我这就不班门弄斧了，推荐一个

《代码随想录》

，B站上也有他的教程，很nice!

这也说明了用动态规划求解的问题不能用贪心算法来求解，那么反过来了？答案我留到最后，至于为什么，请自行查找。

使用二维数组的情况

先直接上代码。

#include<iostream>
#include<vector>
//bits/stdc++.h文件在实际开发中不要使用
//在VScode中似乎已经限制了bits/c++.h的使用。
// #include<bits/stdc++.h>
using namespace std;

//0-1背包问题
void test_2_wei_bag_problem1(){
    vector<int> weight ={1,3,4};
    vector<int> value = {15,20,30};
    int bagweight = 4;
    //二维数组 
    vector<vector<int>> dp(weight.size(),vector<int>(bagweight+1,0));
    //初始化
    for(int j=weight[0];j<=bagweight;j++){
        dp[0][j] = value[0];
    }

    //weight数组的大小 就是物品个数
    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]);

        }
    }

    cout<<dp[weight.size()-1][bagweight]<<endl;
}


int main()
{
    test_2_wei_bag_problem1();
    
    //system("pause");
    //如果需要在VScode中运行出命令控制台，请加上。
}

代码中已经有比较详细的注释了，在此只提以下两点：

1.dp[i] [j] 表示背包重量为j时，装有i个物品时的总价值；

2.递推关系式为dp [i] [j] = max(dp [i-1] [j],dp [i-1] [j-weight[i]]+value[i])。

使用一维数组的情况

直接上代码。

#include <iostream>
#include <vector>

using namespace std ;

void test_0_1_bag_problem(){
    vector<int> weight = {1,3,4};
    vector<int> value = {15,20,30};

    int bagweight = 4;

    vector<int> dp(bagweight+1 ,0); 
    // dp[j]数组 表示重量为j的的背包里最多可装物品的价值
    // 初始化为0，避免大数覆盖遍历结果。
    for(int i=0;i<weight.size();i++){
        for(int j=bagweight;j>=weight[i];j--) //循环条件： 当包中还可以将第i个物品装下为止。
        {
            dp[j] = max(dp[j],dp[j-weight[i]] + value[i]); //递推关系式 dp[j] = max(dp[j] , dp[j-weight[i]] + value[i])
        } 
    }
    cout<<dp[bagweight]<<endl;

}

int main(){
    test_0_1_bag_problem();
    //system("pause");
    return 0;
}

同样也是两个要点：

1. dp[j] 表示重量为j的的背包里最多可装物品的价值；

2. 递推关系 dp[j] = max(dp[j],dp[j-weight[i]] + value[i])。

这里还需要注意的是，为了防止从前往后遍历的情况下，大数覆盖递推结果及同类物品被重复添加的问题，采用了从后往前的遍历方法。及dp[j] = max(dp[j],dp[j-weight[i]] + value[i])。

能用贪心算法求解的问题是可以用动态规划来求解的，但是耗费的时间会更多，所以没必要这样做。



参考于《代码随想录》