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

1.  
   #include<iostream>
2.  
   using namespace std;
3.  
   typedef struct Item {
4.  
   int weight;
5.  
   int value;
6.  
   }Item;
7.  
    
8.  
   Item item[1007];
9.  
   int dp[1007][1007];
10.  
    int maxWeight,n;
11.  
     
12.  
    int main() {
13.  
    cin >> n >> maxWeight;
14.  
    if (n >= 1007 || maxWeight >= 1006) {
15.  
    return 0;
16.  
    }
17.  
    for (int i = 0;i < n;i ) {
18.  
    cin >> item[i].weight >> item[i].value;
19.  
    }
20.  
    //初始化,dp[0][j]
21.  
    for (int i = 0;i <= maxWeight;i ) {
22.  
    if (i >= item[0].weight) {
23.  
    dp[0][i] = item[0].value;
24.  
    }
25.  
    }
26.  
    //遍历数组
27.  
    for (int i = 1;i < n;i ) {
28.  
    for (int j = 1;j <= maxWeight;j ) {
29.  
    if (j - item[i].weight >= 0) {
30.  
    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - item[i].weight] item[i].value);
31.  
    }
32.  
    else {
33.  
    dp[i][j] = dp[i - 1][j];
34.  
    }
35.  
    }
36.  
    }
37.  
    cout << dp[n - 1][maxWeight] << endl;
38.  
    return 0;
39.  
    }

结束！