[Leetcode - Dynamic Programming] Partition Equal S

qpal 发布于2019-08-14 16:41 / 3147人阅读

摘要：背包问题假设有个宝石，只有一个容量为的背包，且第个宝石所对应的重量和价值为和求装哪些宝石可以获得最大的价值收益思路我们将个宝石进行编号，寻找的状态和状态转移方程。我们用表示将前个宝石装到剩余容量为的背包中，那么久很容易得到状态转移方程了。

Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.
Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

1.解题思路
此问题属于动态规划中的背包问题。
背包问题：假设有n个宝石，只有一个容量为C的背包，且第i个宝石所对应的重量和价值为w[i]和v[i],求装哪些宝石可以获得最大的价值收益？
思路：我们将n个宝石进行编号，0,1,2...n-1,寻找DP的状态和状态转移方程。我们用dpij表示将前i个宝石装到剩余容量为j的背包中，那么久很容易得到状态转移方程了。（宝石从0开始编号，所以dpij是在考虑第i-1个宝石装包的情况，当然我们要先初始化前0个宝石装包的情况，即dp0=0,因为不装任何宝石，所以无论如何价值都为0.）

dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
背包无法再装下第i-1个宝石-> dp[i-1][j];
继续将第i-1个宝石装包->  dp[i-1][j-w[i-1]]+v[i-1]。

搞清楚了背包问题，这个Partition Equal Subset Sum的题目就迎刃而解了。
1). 判断数组中所有数的和是否为偶数，因为奇数是不可能有解的；
2). 根据背包问题，取前i个数，体积为j的情况下，

dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-nums[i-1]]+nums[i-1])

3).如果最后dpnums.length=sum/2,则返回true.

2.代码

public class Solution {
    public boolean canPartition(int[] nums) {
        if(nums.length==0) return false;
        int sum=0;
        for(int n:nums){
            sum+=n;
        }
        if(sum%2==1) return false;
        sum=sum/2;
        int[][] dp=new int[nums.length+1][sum+1];
        for(int i=0;i<=nums.length;i++){
            for(int j=0;j<=sum;j++){
                if(i==0) //表示前0个数，所以价值均为0；
                    dp[i][j]=0;
                //在装第i-1个数时，先判断剩余容量j是否大于nums[i-1]
                else if(j

GPU云服务器云服务器 dynamic-programming equal sqlserver_partition LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66252.html

[LeetCode] 698. Partition to K Equal Sum Subsets

Problem Given an array of integers nums and a positive integer k, find whether its possible to divide this array into k non-empty subsets whose sums are all equal. Example 1:Input: nums = [4, 3, 2, 3,...

kuangcaibao 2019-08-16 13:41 评论0 收藏0
[LeetCode] 663. Equal Tree Partition

Problem Given a binary tree with n nodes, your task is to check if its possible to partition the tree to two trees which have the equal sum of values after removing exactly one edge on the original tr...

coordinate35 2019-08-16 13:48 评论0 收藏0
[Leetcode-Dynamic Programming]Unique Binary Search

Unique Binary Search TreesGiven n, how many structurally unique BSTs (binary search trees) that store values 1...n? For example,Given n = 3, there are a total of 5 unique BSTs. 1 3 3 ...

MartinDai 2019-08-16 10:27 评论0 收藏0
leetcode416. Partition Equal Subset Sum

摘要：题目要求假设有一个全为正整数的非空数组，将其中的数字分为两部分，确保两部分数字的和相等。而这里的问题等价于，有个物品，每个物品承重为，问如何挑选物品，使得背包的承重搞好为所有物品重量和的一般。题目要求 Given a non-empty array containing only positive integers, find if the array can be partitio...

Caicloud 2019-08-16 15:10 评论0 收藏0
[LeetCode] 416. Partition Equal Subset Sum

Problem Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Note:Each of the array ...

makeFoxPlay 2019-08-16 13:42 评论0 收藏0