背包問題分類見下圖
參考學習點擊：代碼隨想錄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] + " ");}}
