力扣0/1背包问题：416/494

98 阅读 0 评论 65 点赞

我是靠谱客的博主风趣水蜜桃，最近开发中收集的这篇文章主要介绍力扣0/1背包问题：416/494，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

背包问题0/1背包；

力扣：416-填加减号

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个表达式：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for(int num : nums) sum += num;
        if(S > sum || (S + sum) % 2 == 1) return 0;
        //背包容量target；
        int target = (S + sum) / 2;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int num : nums){
            for(int j = target; j >= num; j--){
                dp[j] = dp[j] + dp[j - num];
            }
        }
        return dp[target];
    }

力扣：494-目标和：

【1，2，3，6】-》【1，2，3】/【6】

public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i:nums){
            sum+=i;
        }
        if(sum%2==1) return false;
        int target = sum/2;
        int[] dp = new int[target+1];
        dp[0] = 1;
        int count=0;
        for(int num:nums){
            for(int k=target;k>=num;k--){
                dp[k]+=dp[k-num];
                System.out.println(dp[k]);
            }
        }
       
        return dp[target]!=0;