01 背包问题的材料看下来，我总结了一句话，物品一件一件减少，背包一点一点变大。

01 背包问题形容

• 最根本的 01 背包问题形容是，有一个限重 W 的背包，有好几件分量为 weight，价值为 value 的物品供你筛选，要在不超过背包限重的前提下，奇妙地抉择物品，使得背包外面的物品价值最大。
• 面试口试遇到的是 01 背包问题的应用题，重点在于把原始问题转化为背包问题，就跟做数学题套公式有点像，把题目中的已知条件跟背包限重 W，以及物品的分量 weight 和价值 value 对应起来，问题就会迎刃而解。

动归三部曲

因为 01 背包问题过于常见，递推公式很容易就能背下来，有人写 dp 时对初始化也比拟佛系，思考深度不够。然而深刻理解 01 背包问题的推导和初始化，对了解动静布局的实质意义重大。

题目举例：W = 4 weight=[1,3,4] value=[15,20,30]

1. 定义 dp 数组

这时须要把物品一件一件减少，背包一点一点变大这句话放在心里。

• 一共有三件物品能够选，所谓物品一件一件减少就是这样，第一次没物品能够挑，第二次 1 件物品能够挑，第三次 2 件物品能够挑 … 每步都多出了一件物品供本人筛选，那本人就能够决定，放进去还是不放了。
• 限重为 4，所谓背包一点一点变大就是这样，4 的限重太大，先从限重为 0 开始算起，直到达到 4 为止。

最终 dp 是一个 3 * 5 的数组，dp[i][j]的含意就是有 0 - i 件物品供你筛选，放入容量为 j 的背包能取得的最大价值。

（对于动静布局问题的剖析，要始终牢记 dp 的含意）

那最初的后果就是有 0 - 2 件物品供你筛选，放入容量为 4 的背包能取得的最大价值，天然是数组右下角那个格子 dp[2][4] 了。

2. 递推公式

递推公式怎么去想呢？外围就是每次多了件物品能够挑，要辨别这个物品到底要不要放进背包。

• 这个物品要

dp[i][j] = dp[i-1][j] 比如说 0 - 2 件物品供你挑，限重 j，那你决定不要第 2 件物品，那好，背包限重没变，这个时候背包的价值就是 0 - 1 件物品供你挑，限重 j 时计算的最大价值 dpi-1（也能够了解成，这个物品要是不拿，就跟没他没什么区别，所以还是之前没他时候，即 i - 1 时的最大价值）。

• 这个物品不要

dp[i][j] = dp[i-1][j-weight[i]]+value[i] 比如说 0 - 2 件物品供你挑，限重 j，那你决定要第 2 件物品，那好，这个时候背包装的价值必定先把这件物品的价值给算上，那剩下的价值呢，就给 0 - 1 件物品去实现吧，只不过因为我放了第 2 件物品，背包的限重变少了 weight[i]。

• 取最大价值 可挑可不挑，那就看看哪个价值大就选哪个作为最大价值。

递推的程序就是下图了

3. 初始化

要初始化的中央就是递推不到的地位，而后算别的 dp[i][j] 的时候须要用到的值。图中就是第 0 列和第 0 行。

• 第 0 列 限重 0，无论多少物品那都没的放，价值必定为 0，所以第 0 列全 0。
• 第 0 行 有第 0 件物品能够挑，那如果限重 >= 这个物品，就代表物品能够放进去，价值就是这个物品的值。

C++ 代码实现 含具体正文

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int W = 4;// 限重
    int weight[3] = {1,3,4};// 物品分量
    int value[3] = {15,20,30};// 物品价值
    vector<vector<int>> dp(3,vector<int>(W+1,0)); //3* 5 的 dp
    // 初始化
    for(int i = 0;i < 3;i++){dp[i][0] = 0;
    }
    for(int j = 1;j <= W;j++){if(j >= weight[0]) dp[0][j] = value[0];
    }
    // 递推
    for(int i = 1;i < 3;i++){for(int j = 1;j <= 4;j++){dp[i][j] = dp[i-1][j];// 不拿这件物品
            if(j >= weight[i])// 下标不越界 或者说之后限重 >= 物品能力拿物品
                // 拿这件物品和不拿这件物品 找最大
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
        }
    }
    // 打印下 dp
    for(int i = 0; i < 3;i++){for(int j = 0;j <=4;j++){cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    cout << dp[2][4];// 最终后果
    return 0;
}

手推一次 dp 数组加深了解 为优化打基础

手推时，发现能够先把上一行的数据整体挪动下来，当限重 >= 该物品分量时再思考如果筛选这个物品价值是多少，选更大价值即可(要是限重小了那这个物品必定不能放，只能从上一行移下来了)。

手推二维 dp 数组能够为滚动数组优化做铺垫。

滚动数组优化

滚动数组要着重了解的是初始化和遍历程序的问题。

动归三部曲

1. 定义 dp 数组

依据手推 dp 数组中的教训咱们能够晓得，算下一行是先把上一行的数据给搬下来了。所以优化时能够只用一行格子，而不必全副的格子。

dp[j] 含意就是限重 j 时的最大价值。一件物品一件物品去迭代，返回的是最初一个格子的值。

2. 递推

！用一排格子就得思考一个问题，值笼罩了怎么办？

在二维 dp 中，显然咱们用到了上方和左上方的值，那一维 dp 就会用到原地和左方的值。那要是从左往右算，值变了咋整，不就不是上一轮完结的 dp 了吗。所以只能 == 倒着往前遍历 ==，就不会有这种事了，反正 dp[i]算的时候又跟前面的值没关系。

下图所示的是迭代到第 1 件物品时要用到的其余值。(weight[2] = 3, 所以只须要算限重 3 和 4。绿色是橙色格子在递推时须要用到的值)

3. 初始化

当然能够像为二维 dp 初始化第一行一样初始化一维 dp, 而后从第 1 件物品开始迭代。但其实能够初始化为全 0，从第 0 件物品开始迭代，成果一样。

测验全 0 的初始化对不对，次要看第 0 件物品的迭代是否正确。此时发现，依然是当限重 >=weight[0]时，
dp[i]=max(dp[i],dp[i-weight[i]]+value[i])=max(0,value[i])=value[i]。

C++ 代码加正文

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int W = 4;// 限重
    int weight[3] = {1,3,4};// 物品分量
    int value[3] = {15,20,30};// 物品价值
    vector<int> dp(W+1,0); // 5 的 dp
    // 初始化 全 0
    // 递推
    for(int i = 0;i < 3;i++){for(int j = 4;j >= 0;j--){if(j >= weight[i]) 
                dp[j] = max(dp[j],dp[j-weight[i]]+value[i]); 
        }
    }
    cout << dp[4];// 最终后果
    return 0;
}