代码随想录day36：动态规划part4，背包问题

day36：动态规划part4，背包问题

01背包

https://kamacoder.com/problempage.php?pid=1046

二维数组版本：

dp[i][j]里的i和j表达的是什么了，i是物品，j是背包容量。

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        int[] values = new int[m];
        int[] weights = new int[m];
        for (int i = 0; i < m; i++) weights[i] = in.nextInt();
        for (int i = 0; i < m; i++) values[i] = in.nextInt();
        int[][] dp = new int[m][n + 1];
        for (int i = weights[0]; i <= n; i++) dp[0][i] = values[0];
        for (int i = 1; i < m; i++) {
            for (int j = 1; j <= n; j++) {
                if (j < weights[i])
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
            }
        }
        System.out.println(dp[m - 1][n]);
    }
}

压缩为一维滚动数组版本：

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        int[] values = new int[m];
        int[] weights = new int[m];
        for (int i = 0; i < m; i++) weights[i] = in.nextInt();
        for (int i = 0; i < m; i++) values[i] = in.nextInt();
        int[] dp = new int[n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = n; j >= weights[i]; j--)
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
        
        System.out.println(dp[n]);
    }
}

416.分割等和子集

01背包应用

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % 2 == 1) return false;
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for (int i = 0; i < n; i++) {
            for (int j = target; j >= nums[i]; j--)
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            if (dp[target] == target) return true;
        }
        return false;
    }
}