背包问题动态规划编程题集合（leetcode)

动态规划步骤

确认dp数组含义，求递推公式，进行dp数组初始化，遍历顺序，打印

01背包问题，每件物品只有一样，我们的选择是拿或者不拿；于完全背包问题，每件物品有无数个，同样求解将哪些物品放入背包中，可以使得背包放入物品的总价值最大：

给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。

根据数组的长度 nn 判断数组是否可以被划分。如果 n<2，则不可能将数组分割成元素和相等的两个子集，因此直接返回 false。计算整个数组的元素和sum如果 sum 是奇数，则不可能将数组分割成元素和相等的两个子集，因此直接返回 false。如果sum 是偶数，则令 target= sum/2,需要判断是否可以从数组中选出一些数字，使得这些数字的和等于target。在这里nums数组中的每个值都相当于背包问题的重量和价值，如果最大价值等于target则就可以划分两个子集。

  public boolean canPartition(int[] nums) {        if(nums.length<2)            return false;        int sum = Arrays.stream(nums).sum();        if(sum%2!=0)            return false;        int target = sum / 2;        int[][] dp=new int[nums.length+1][target+1];        for(int i=1;i<dp.length;i++){            for(int j=1;j<dp[0].length;j++){                if(nums[i-1]>j)                    dp[i][j]=dp[i-1][j];                else                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-nums[i-1]]+nums[i-1]);            }        }        return dp[nums.length][target]==target;    }

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

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

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1”

返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

输入：nums = [1,1,1,1,1], target = 3

输出：5

解释：一共有 5 种方法让最终目标和为 3 。

-1 + 1 + 1 + 1 + 1 = 3

+1 – 1 + 1 + 1 + 1 = 3

+1 + 1 – 1 + 1 + 1 = 3

+1 + 1 + 1 – 1 + 1 = 3

+1 + 1 + 1 + 1 – 1 = 3

引用官方图片

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int n = nums.length, neg = diff / 2;
        int[][] dp = new int[n + 1][neg + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= neg; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= num) {
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[n][neg];
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/target-sum/solution/mu-biao-he-by-leetcode-solution-o0cp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

完全背包

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

输入：amount = 5, coins = [1, 2, 5]

输出：4

解释：有四种方式可以凑成总金额：

5=5

5=2+2+1

5=2+1+1+1

5=1+1+1+1+1

 public int change(int amount, int[] coins) {
        int[][] dp=new int[coins.length+1][amount+1];
        dp[0][0]=1;
        for (int i=1;i<dp.length;i++){
            for(int j=0;j<dp[0].length;j++){
                dp[i][j]=dp[i-1][j];
                if(coins[i-1]<=j)
                    dp[i][j]+=dp[i][j-coins[i-1]];
            }
        }
        return dp[coins.length][amount];
    }

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/143058.html

背包问题动态规划编程题集合（leetcode)

相关推荐

发表回复

分享到: