代码随想录算法训练营第41天

今日任务

● 01背包问题，你该了解这些！ ● 01背包问题，你该了解这些！滚动数组
● 416. 分割等和子集

链接：https://docs.qq.com/doc/DUGdkaEl5dFN1QnBl (opens in a new tab)

背包问题总览

01背包问题

01背包每个物品只能取一次

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

若dp使用一维数组，即dp[j] 表示容量为j的背包，价值总和最大是多少。但是这样的话，我们需要从后往前遍历容量，避免重复计算物品。此时只能先遍历物品再遍历容量。

416. 分割等和子集

自己想法

将数组内的数看作物品，其价值和重量都是这个数，

将数组和的一半看作背包的容量，转化为01背包问题。

最终判断此时背包内最大价值是否==背包容量。

class Solution {
    public boolean canPartition(int[] nums) {
        int num_sum = Arrays.stream(nums).sum();
        if (num_sum % 2 != 0) return false;
        int bagSize = num_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]);
            }
        }
        // System.out.println(Arrays.toString(dp));
        if (dp[bagSize] == bagSize) return true;
        else return false;
    }
}