0-1背包問題就是各個物品數(shù)量只有一個

KamaCoder 46

題目鏈接：攜帶研究材料

二維數(shù)組解法

兩點注意：

1. 不需要對物品價值進行
2. 二維數(shù)組遍歷容量要從1開始指煎，而不是當前物品所需空間，是為了把值傳遞下去

import java.util.*;
 
public class Main{
    public static void main (String[] args) {
        /* code */
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        int volumn = in.nextInt();
        int[] space = new int[num];
        int[] value = new int[num];
        for(int i=0; i<num; i++){
            space[i] = in.nextInt();
        }
        for(int i=0; i<num; i++){
            value[i] = in.nextInt();
        }
         
        int[][] dp = new int[num+1][volumn+1];
         // 不需要對物品價值進行
         // 二維數(shù)組遍歷容量要從1開始昌讲，而不是當前物品所需空間，是為了把值傳遞下去
        for(int i=1; i<=num; i++){
            for(int j=1; j<=volumn; j++){
                if(j>=space[i-1]){
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-space[i-1]] + value[i-1]);
                }
                else dp[i][j] = dp[i-1][j];
            }
        }
         
        System.out.println(dp[num][volumn]);
    }
}

一維數(shù)組解法

兩點注意：

1. 不需要從最小的物品開始遍歷
2. 一維滾動數(shù)組需要容量從后往前遍歷减噪，為的就是0-1背包中短绸，物品只能取一次

import java.util.*;
 
public class Main{
    public static void main (String[] args) {
        /* code */
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        int volumn = in.nextInt();
        int[] space = new int[num];
        int[] value = new int[num];
        for(int i=0; i<num; i++){
            space[i] = in.nextInt();
        }
        for(int i=0; i<num; i++){
            value[i] = in.nextInt();
        }
         
        int[] dp = new int[volumn+1];
        // 不需要從最小的物品開始遍歷
        
        for(int i=0; i<=num; i++){
            //一維滾動數(shù)組需要容量從后往前遍歷
            //為的就是0-1背包中车吹，物品只能取一次
            for(int j=volumn; j>=space[i]; j--){
                dp[j] = Math.max(dp[j], dp[j-space[i]] + value[i]);
            }
        }
         
        System.out.println(dp[volumn]);
    }
}

LeetCode 416

題目連接：分割等和子集
這道題主要是要想到使用01背包問題取解決
注意點：int sum =Arrays.stream(nums).sum();直接使用流來計算數(shù)組總和

class Solution {
    public boolean canPartition(int[] nums) {
        int sum =Arrays.stream(nums).sum();
        if(sum%2==1) return false;
        int bagSize = sum/2;

        int[] dp = new int[bagSize+1];

        for(int i=0; i<nums.length; i++){
            for(int j=bagSize; j>=nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[bagSize] == bagSize;
    }
}