0-1背包问题小结

使用二维数组的情况

先直接上代码。

#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])。

参考于《代码随想录》

@AHU_IAI_Threemen-ZL