01背包
标准的01背包问题：
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
暴力法：回溯搜索，O(2^n)
使用动态规划
1.二维dp数组
实现步骤：
1.确定dp数组及其下标含义
dp[i] [j] 代表 从0到i任选物品，放进容量为j的背包所得的最大价值
2.确定递推公式
对于当前点有两种情况
(1)放进背包
此时的价格变为dp[i] [j] = dp[i- 1] [j - weight[i]] + values[i]
(2)不放进背包
当前剩余容量不满足物品要求dp[i] [j] = dp[i - 1] [j]
最后要求价值最高。所以要在两者之间取最大值
递推数组：dp[i] [j] = max(dp[i-1] [j], dp[i-1] [j-weight[i]] + values[i] )
3.初始化dp数组
根据递推公式可知一个点是由该点左边和上边的点推导出来，先初始化dp[0] [j]一行和dp[i] [0]一列
dp[0] [j] 一行
满足第一个物品重量的初始化化为第一个物品的价值，不满足的初始化为0
dp[i] [0] 一列
没有重量，初始化为0即可
4.确定遍历顺序
因为当前点的状态是由上方和左上方的状态推导，所以一行一行遍历和一列一列遍历都可以
5.举例推导dp数组
可以举个例子或者根据测试用例和自己的递推公式进行推导，验证自己前面几步的正确性，或者在提交不过后打印日志，手动推导dp数组来debug
实现代码(以Java为例)：
public class demo1 {
//01背包理论实践
//二维dp数组
public static void main(String[] args) {
int[] weight = {3, 4, 1};
int[] value = { 20, 30, 10};
int bagSize = 5;
System.out.println(bag_01(weight, value, bagSize));
}
/**
* 有n件物品和一个最多能背重量为w 的背包。
* 第i件物品的重量是weight[i]，得到的价值是value[i]
* 。每件物品只能用一次，求解将哪些物品装入背包里物品
* 价值总和最大。
*/
public static int bag_01(int[] weight, int[] value, int bagSize) {
int n = weight.length;
int m = bagSize;
//行代表背包的容量，从0开始
//列表示物品，从0小标开始
int dp[][] = new int[n + 1][m + 1];
for(int i = 0; i <= n; i++) {//初始化列
dp[i][0] = 0;
}//初始化列都为0可以省略，为了思路更有逻辑在这里列出来
for(int j = 1; j <= m && weight[0] <= j ; j++) {
dp[0][j] = value[0];
}
//遍历顺序按行按列两种都行
for(int i = 1; i < n; i++) {
for(int j = 1; j <= m; j++) {
if(j < weight[i]) dp[i][j] = dp[i - 1][j];
else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}
//打印一下dp数组
for(int i = 0; i < n; i++) {
for(int j = 0; j <= m; j++) {
System.out.print(dp[i][j] + " ");
}
System.out.println();
}
System.out.println("===============");
return dp[n - 1][m];
}
}
2.一维dp数组(滚动数组)
因为之前是靠上一层推导出下一层，可以将二维矩阵压缩成一个一维dp数组，就是滚动数组，不断利用之前的值，即将上一次已经计算好的值拷贝到单层，变成一维数组
实现步骤：
1.确定dp数组及其下标含义
将前文所述的二维数组dp[i] [j]压缩为滚动数组dp[j],dp[j]代表了重量为j的背包所能容纳的最大价值
2.确定递推公式
(1)不放入背包，即背包容量小于物品
dp[j] = dp[j]，因为此时的dp[j]就相当于二维的dp[i - 1] [j]
(2)放入背包
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
3.初始化dp数组
动态规划中初始化这步也很重要，需要想清楚
这题dp[j]代表重量为j的背包能容纳的最大价值，一开始都初始化为0就行，表示没有物品放入背包
4.确定遍历顺序
首先肯定要遍历每一个物品，物品在外层循环
内层循环遍历背包，注意遍历顺序，如果是从左到右遍历会出现一个物品重复使用的情况，因为此时外层循环是相同的物品，从左往右遍历使用了前面的状态相当于使用了相同的物品，所以要从右往左遍历。这里可以有一个优化的点，即内层循环不考虑容量小于当前物品重量的背包
5.举例推导dp数组
实现代码(以Java为例)：
public class demo2 {
public static void main(String[] args) {
int[] weight = {1, 3, 4};
int[] value = {15, 20, 30};
int bagSize = 4;
System.out.println(bog_02(weight, value, bagSize));
}
//二维矩阵压缩为一维数组，滚动数组
public static int bog_02(int[] weight, int[] value, int bagSize) {
int n = weight.length;
int m = bagSize;
//初始化，默认就是0
int[] dp = new int[m + 1];
for(int i = 0; i < n; i++) {
for(int j = m; j >= weight[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
//打印dp数组
for(int j = 0; j <= m; j++) {
System.out.print(dp[j] + " ");
}
System.out.println();
System.out.println("==============");
return dp[m];
}
}理解01背包问题对于学习动态规划有重要的意义
以上内容是我对在代码随想录学习01背包问题知识点的总结以及收获，希望以上内容能帮助到大家