训练营第四十二天 | 01背包问题,你该了解这些! ● 01背包问题,你该了解这些! 滚动数组 ● 416. 分割等和子集

发布时间:2024年01月12日

?01背包问题?二维?

代码随想录

dp二维数组

优化

?01背包问题?一维?

代码随想录

dp一维数组

?416.?分割等和子集??

把数组分成总和相等的两份,如果数组总和为奇数,不能分割,若有符合的数组子集,返回true

代码随想录

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;//计算总和
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        int target = sum >> 1;//将总和分成相等的两份
        if(sum % 2 == 1) return false;//总和为奇数不可能分割两个完全一样的数组
        int[] dp = new int[target+1];//dp[j]指容量为j时 所容纳的物品最大价值
        for(int i = 0; i < nums.length; 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 dp[target] == target;
    }
}

文章来源:https://blog.csdn.net/Tropic____/article/details/135514609
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。