01背包入门讲解

01背包问题研究的是，给定n件物品以及能够最大承重为maxWeight的背包，第i个物品的重量为item[i].weight,价值为item[i].value.每一件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大?

dp[i][j]含义

根据题干可知，最后的答案dp[n-1][maxWeight]（i下标从0开始）表示求解将n件物品任取放入最大承重为maxWeight的背包，求背包物品的最大价值，因此可知dp[i][j]应该表示将从0~i物品中任取放入最大承重为j的背包里面，求其背包物品的最大价值。

递推公式

下求dp[i][j]的递推公式，由于第i件物品是否放入背包仅仅两种情况：不放与放。

先讨论第i件物品不放入背包的情况，易知，当第i件物品不放入最大承重为j的背包时，背包的价值最大，那么其价值dp[i][j]等于将0~i-1件物品放入最大承重为j的背包时，背包的最大价值dp[i-1][j],

即dp[i][j]=dp[i-1][j]

再讨论第i件物品放入背包的情况，易知，当第i将物品放入最大承重为j的背包时，背包的价值最大，那么其价值dp[i][j]等于0~i-1件物品放入承重为j-item[i].weight的背包时，背包的最大价值dp[i-1][j-item[i].weight]加上第i个物品的价值item[i].value,

即dp[i][j]=dp[i-1][j-item[i].weight]+item[i].value

解释第二种情况，由于唯有从0~i-1件物品任取放入最大承重为j-item[i].weight的背包加上第i件物品的重量才能使新背包的最大承重为j，故dp[i][j]=dp[i-1][j-item[i].weight]+item[i].value

因此，dp[i][j]的递推公式为：

dp[i][j]=max(dp[i-1][j],dp[i]-1[j-item[i].weight]+item[i].value)

dp数组的初始状态

（图片来自代码随想录）

根据上述推导公式可知，dp[i][j]由其上方或左上方的元素推导而来，因此需要初始化数组中最上一行以及最左一行的元素。

显然，dp[i][0]=0表示最大承重为0的背包的最大价值为0；dp[0][j]表示第0个物品装入最大承重为j的背包的物品最大价值。易知，当item[0].weight>=j时,dp[0][j]=item[0].value;否则,dp[0][j]=0.

遍历数组

利用二重循环,物品从第1件物品开始，背包最大承重j从1开始,递推数组的元素dp[i][j]，最终输出dp[n-1][maxWeight].

代码实现

语言：c++,环境：Visual Studio 2022

#include<iostream>
using namespace std;
typedef struct Item {
    int weight;
    int value;
}Item;

Item item[1007];
int dp[1007][1007];
int maxWeight,n;

int main() {
    cin >> n >> maxWeight;
    if (n >= 1007 || maxWeight >= 1006) {
        return 0;
    }
    for (int i = 0;i < n;i++) {
        cin >> item[i].weight >> item[i].value;
    }
    //初始化,dp[0][j]
    for (int i = 0;i <= maxWeight;i++) {
        if (i >= item[0].weight) {
            dp[0][i] = item[0].value;
        }
    }
    //遍历数组
    for (int i = 1;i < n;i++) {
        for (int j = 1;j <= maxWeight;j++) {
            if (j - item[i].weight >= 0) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - item[i].weight] + item[i].value);
            }
            else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    cout << dp[n - 1][maxWeight] << endl;
    return 0;
}

结束！