基础01背包

问题概述

n种物品每种只有1个。

每个物品有自己的weight和value，求解一个MAX_Weight的容量的背包尽可能多装value的解法。

背包MAX重量为4。

每个物品只有2个状态（0或1），直接用回溯算法进行枚举。解决本题的时间复杂度为O(2^n) = 8。

一个二维数组，

下标i 对应条件0~i 的物品任取，下标j 对应背包重量。

dp[i][j] 的值对应当0~i的物品任取、一个容量为j的背包所放物品的最大value。

考虑一个dp[i][j]的前后。

首先dp[i][j]前面说过，代表i、j情况下的最大value，

那么不放物品i的最大价值：dp[i-1][j]（不考虑放入物品i但保持j背包重量的情况下的最大价值）

从而推出放物品i的最大价值：dp[i-1][j-weight[i]] + value[i]（一定放物品i的背包的最大价值）

从上面的递进关系可以推出公式，dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]) ;

利用推出的公式dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]) ;

![image-20220112140432011](E:\My Github\hexo\blog\source_posts\Tech\Game\01knapsack.assets\image-20220112140432011.png)

因为所有的数据都是 max(正上方数据，左上角某一个数据 + value[i])。所以初始化只要把第一行和第一列正确初始化，其他的都可以靠递推公式推出。

第一列因为背包容量为0所以固定全是0，而第一行很容易计算。

最后初始化完成结果如图：

二维dp数组其实都可以（因为确定数值时左上方的数值都已确定），但是常规选择：

1
2
3

for(物品)
    for(背包)
        递推公式 dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);