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;}