二維：

1.dp[i][j] 表示從下標為[0-i]的物品里任意取，放進容量為j的背包，價值總和最大是多少。

2.遞歸公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3.初始化：

????????首先從dp[i][j]的定義出發，如果背包容量j為0的話，即dp[i][0]，無論是選取哪些物品，背包價值總和一定為0。

????????那么很明顯當 j < weight[0]的時候，dp[0][j] 應該是 0，因為背包容量比編號0的物品重量還小。當j >= weight[0]時，dp[0][j] 應該是value[0]，因為背包容量放足夠放編號0物品。

? ? ? ? 其他位置下標初始-1，初始-2，初始100，都可以

4.遍歷順序：先物品再背包或者先背包再物品

5.打印dp

滾動數組：滾動數組了，就是把二維dp降為一維dp

如果把dp[i - 1]那一層拷貝到dp[i]上，表達式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

與其把dp[i - 1]這一層拷貝到dp[i]上，不如只用一個一維數組了，只用dp[j]（一維數組，也可以理解是一個滾動數組）。

1.在一維dp數組中，dp[j]表示：容量為j的背包，所背的物品價值可以最大為dp[j]。

2.遞推公式：此時dp[j]有兩個選擇，一個是取自己dp[j] 相當于 二維dp數組中的dp[i-1][j]，即不放物品i，一個是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，畢竟是求最大價值

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3.初始化：

dp[j]表示：容量為j的背包，所背的物品價值可以最大為dp[j]，那么dp[0]就應該是0，因為背包容量為0所背的物品的最大價值就是0。

那么dp數組除了下標0的位置，初始為0，其他下標應該初始化多少呢？

類似于從二維數組的i = 1層分析

看一下遞歸公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

dp數組在推導的時候一定是取價值最大的數，如果題目給的價值都是正整數那么非0下標都初始化為0就可以了。

這樣才能讓dp數組在遞歸公式的過程中取的最大的價值，而不是被初始值覆蓋了。

那么我假設物品價值都是大于0的，所以dp數組初始化的時候，都初始為0就可以了。

4.遍歷順序：

只能從后先前：從前向后會將同一物品反復計算。

只能先物品，先背包的話沒有意義。（結合dp數組含義自己模擬一下）

如果遍歷背包容量放在上一層，那么每個dp[j]就只會放入一個物品，即：背包里只放入了一個物品。

5.打印dp