<aside> 💡

动规五部曲：

1. 明确DP数组与其下标的含义
2. 确定递推公式
3. 确定DP数组初始化方式
4. 确定遍历顺序
5. 打印DP数组进行debug </aside>

0-1背包理论基础

基础

DP数组与其下标的含义

dp[i][j]

• i为物品编号，j为背包容量
• dp[i][j]表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

value[i]

• 物品i的价值，一般以题目需要优化的目标值作为value

weight[i]

• 物品i的重量，其含义一般与背包容量的含义相同

递推公式

分类：是否要放入下标为i的物品：

• 不放时最大价值为：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])

DP数组初始化

dp[i][j]由其上方格子和左上方范围内某一个格子初始化而来，所以需要初始化最上的一行和最左的一列：

• i = 0时，对于j < weight[0]的格子，初始化为0，往后的格子初始化为value[0]
• j = 0时，背包容量为0，装不下任何物品，所以最左列全部初始化为0

遍历顺序

先遍历物品（i）或先遍历背包（j）都可以，都能将dp数组填满

滚动数组优化