【动态规划】经典01背包（装满及不装满）问题c++代码，二维数组变一位数组

01经典背包问题

01背包问题代码整理

困扰小白的经典动态规划中的背包问题。整理了牛客力扣上题解和个人理解，形成了一篇完整的代码。包括了二维数组和一维数组和恰好装满问题与不要求装满得到的最大价值。

代码展示

可在本地ide进行调试学习

#include 
using namespace std;
#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX - 1)

//如果不要求背包恰好装满，则无论如何都可以不放，因此数组初始化为0.
//如果要求背包恰好装满，则初始化为最大价值的最小值，即−INF表示没装满
//这样如果上一层j−v[i]的背包没装满，下一层还是装不满，−INF+w[i]仍为一个很小的负数。
//同时背包容量为0时，恰好装满等价于什么也不装，因此同时初始化dp[0]=0.

int main() {
    int n = 3,V = 5; // 共有3个物品，背包容量为5
    vector<int> v = {2,4,1};
    vector<int> w = {10,5,4};
    //物品   体积   价格
    //0      2      10
    //1      4      5
    //2      1      4

    //二维数组求这个背包至多能装多大价值的物品；
    //初始数组全都为0；初始化第一个物品i-1即第一行初值
    vector<vector<int>> dp1(n,vector<int>(V+1,0));
    
    for(int j = 0; j < V+1; j++){
        if(j >= v[0])
            dp1[0][j] = w[0];
        else
            dp1[0][j] = 0;
    }
    

    for(int i = 1; i < n; i++)
        for(int j = 0; j < V+1; j++){
            if(j < v[i])
                dp1[i][j] = dp1[i-1][j];
            else
                dp1[i][j] = max (dp1[i-1][j-v[i]]+w[i], dp1[i-1][j]);
        }
    
    cout << dp1[n-1][V]  << endl;

    //二维数组求背包恰好装满能装物品的最大价值
    //初始化数组为-无穷，dp[0][0] = 0；
    vector<vector<int>> dp2(n,vector<int>(V+1,0));
    int ans2 = 0 ;
    for(int i = 0;i < n;++i)
        for(int j = 0;j < V+1; ++j)
            dp2[i][j] = INT_MIN;
    dp2[0][0] = 0;
    for(int i = 1;i < n;++i){
        for(int j = 0;j <= V;++j){
            if(j >= v[i])
                dp2[i][j] = max(dp2[i - 1][j - v[i]] + w[i],dp2[i - 1][j]);
            else
                dp2[i][j] = dp2[i - 1][j];
        }
    }
    if(dp2[n-1][V] < 0)
        ans2 = 0;
    else
        ans2 = dp2[n-1][V];
    cout << ans2 << endl;
    
    //打印dp1数组
    for(int i = 0;i < n; ++i){
        for(int j = 0;j < V+1; ++j){
             cout << dp1[i][j] << " ";
        }
        cout << endl;   
    }

    //打印dp2数组    
    for(int i = 0;i < n; ++i){
        for(int j = 0;j < V+1; ++j){
             cout << dp2[i][j] << " ";
        }
        cout << endl;   
    }


    //一维数组求这个背包至多能装多大价值的物品；
    //倒序遍历
    vector<int> dp3(V+1,0);
    for(int i = 0; i< n; i++){
        for(int j = V; j >= v[i]; j--){
            dp3[j] = max(dp3[j], dp3[j-v[i]]+w[i]);
        }
    //打印dp3数组
        for(int i = 0; i <= V; i++){
            cout << dp3[i] << " ";
        }
        cout << endl;
    }

    //一维数组求背包恰好装满能装物品的最大价值
    vector<int> dp4(V+1,INT_MIN);
    dp4[0] = 0;
    for(int i = 0; i< n; i++){
        for(int j = V; j >= v[i]; j--){
            dp4[j] = max(dp4[j], dp4[j-v[i]]+w[i]);
        }
    //打印dp3数组
        for(int i = 0; i <= V; i++){
            cout << dp4[i] << " ";
        }
        cout << endl;
    }
}

结果显示