背包问题分类见下图
参考学习点击：代码随想录01背包讲解
01背包问题：
核心思路：
1、先遍历物品个数，再遍历背包容量。因为容量最先是最大的，往背包里放物品，所以背包容量在慢慢减少，但背包容量需要大于每一个物品体积
2、每个物品有2个选择：选中和不选中。
3、选中的结果是背包剩余容量的最大价值+选中物品的价值；
4、不选中的结果是背包剩余容量还是不变，最大价值还是背包剩余容量的最大价值
public static void main(String[] args) {
int[] weight = {1, 3, 4}; //每个物品体积
int[] value = {15, 20, 30}; // 每个物品价值
int bagWight = 4; // 背包容量
testWeightBagProblem(weight, value, bagWight);
}
public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
//定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
int[] dp = new int[bagWeight + 1];//背包容量来定义dp数组
for (int i = 0; i < weight.length; i++){ //先遍历物品
for (int j = bagWeight; j >= weight[i]; j--){ //再遍历背包，背包容量是从最大一直慢慢减少
//每个物品有2种选择，选中与不选中：选中的话，背包价值=背包容量剩余物品的价值在加上选中物品的价值
//不选中的话，背包价值=背包容量j的价值
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
//打印dp数组
for (int j = 0; j <= bagWeight; j++){
System.out.print(dp[j] + " ");
}
}
