[Leetcode - Dynamic Programming] Partition Equal S

qpal 發(fā)布于2019-08-14 16:41 / 3234人閱讀

摘要：背包問題假設(shè)有個寶石，只有一個容量為的背包，且第個寶石所對應(yīng)的重量和價值為和求裝哪些寶石可以獲得最大的價值收益思路我們將個寶石進(jìn)行編號，尋找的狀態(tài)和狀態(tài)轉(zhuǎn)移方程。我們用表示將前個寶石裝到剩余容量為的背包中，那么久很容易得到狀態(tài)轉(zhuǎn)移方程了。

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.解題思路
此問題屬于動態(tài)規(guī)劃中的背包問題。
背包問題：假設(shè)有n個寶石，只有一個容量為C的背包，且第i個寶石所對應(yīng)的重量和價值為w[i]和v[i],求裝哪些寶石可以獲得最大的價值收益？
思路：我們將n個寶石進(jìn)行編號，0,1,2...n-1,尋找DP的狀態(tài)和狀態(tài)轉(zhuǎn)移方程。我們用dpij表示將前i個寶石裝到剩余容量為j的背包中，那么久很容易得到狀態(tài)轉(zhuǎn)移方程了。（寶石從0開始編號，所以dpij是在考慮第i-1個寶石裝包的情況，當(dāng)然我們要先初始化前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];
繼續(xù)將第i-1個寶石裝包->  dp[i-1][j-w[i-1]]+v[i-1]。

搞清楚了背包問題，這個Partition Equal Subset Sum的題目就迎刃而解了。
1). 判斷數(shù)組中所有數(shù)的和是否為偶數(shù)，因為奇數(shù)是不可能有解的；
2). 根據(jù)背包問題，取前i個數(shù)，體積為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個數(shù)，所以價值均為0；
                    dp[i][j]=0;
                //在裝第i-1個數(shù)時，先判斷剩余容量j是否大于nums[i-1]
                else if(j