0-1背包问题就是各个物品数量只有一个

KamaCoder 46

题目链接：携带研究材料

二维数组解法

两点注意：

1. 不需要对物品价值进行
2. 二维数组遍历容量要从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];
         // 不需要对物品价值进行
         // 二维数组遍历容量要从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]);
    }
}

一维数组解法

两点注意：

1. 不需要从最小的物品开始遍历
2. 一维滚动数组需要容量从后往前遍历，为的就是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++){
            //一维滚动数组需要容量从后往前遍历
            //为的就是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();直接使用流来计算数组总和

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;
    }
}