[Leetcode - Dynamic Programming] Partition Equal S

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

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

dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
背包無法再裝下第i-1個(gè)寶石-> dp[i-1][j];
繼續(xù)將第i-1個(gè)寶石裝包->  dp[i-1][j-w[i-1]]+v[i-1]。

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