DP18 分割区间问题 Partition problem @geeksforgeeks

思路：

把能否划分区间的问题转化为能不能找到一个使得和为总和的一半的子区间，然后转为01背包问题，分析每一个元素是否取

Partition problem is to determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is same.

Examples

arr[] = {1, 5, 11, 5}
Output: true 
The array can be partitioned as {1, 5, 5} and {11}

arr[] = {1, 5, 3}
Output: false 
The array cannot be partitioned into equal sum sets.

Following are the two main steps to solve this problem:
1) Calculate sum of the array. If sum is odd, there can not be two subsets with equal sum, so return false.
2) If sum of array elements is even, calculate sum/2 and find a subset of array with sum equal to sum/2.

The first step is simple. The second step is crucial, it can be solved either using recursion or Dynamic Programming.

Recursive Solution
Following is the recursive property of the second step mentioned above.

Let isSubsetSum(arr, n, sum/2) be the function that returns true if 
there is a subset of arr[0..n-1] with sum equal to sum/2

The isSubsetSum problem can be divided into two subproblems
 a) isSubsetSum() without considering last element 
    (reducing n to n-1)
 b) isSubsetSum considering the last element 
    (reducing sum/2 by arr[n-1] and n to n-1)
If any of the above the above subproblems return true, then return true. 
isSubsetSum (arr, n, sum/2) = isSubsetSum (arr, n-1, sum/2) ||
                              isSubsetSum (arr, n-1, sum/2 - arr[n-1])

package DP;

public class PartitionProbelm {

	public static void main(String[] args) {
		int[] A = {3, 1, 5, 9, 12};
		int n = A.length;
		System.out.println(findPartitionRec(A, n));
		System.out.println(findPartitionDP(A, n));
	}

	// A utility function that returns true if there is a subset of arr[]
	// with sun equal to given sum
	public static boolean isSubsetSumRec(int[] A, int n, int sum){
		if(sum < 0){
			return false;
		}
		if(sum == 0){
			return true;
		}
		if(n==0 && sum>0){
			return false;
		}
//		if(A[n-1] > sum){		// If last element is greater than sum, then ignore it
//			return isSubsetSumRec(A, n-1, sum);
//		}
		
		/* else, check if sum can be obtained by any of the following
	      (a) excluding the last element 不选A[n-1]
	      (b) including the last element	选A[n-1]
	   */
		return isSubsetSumRec(A, n-1, sum) || isSubsetSumRec(A, n-1, sum-A[n-1]);
	}

	// Returns true if A[] can be partitioned in two subsets of
	// equal sum, otherwise false
	//	Time Complexity: O(2^n) In worst case
	//	, this solution tries two possibilities (whether to include or exclude) for every element.
	public static boolean findPartitionRec(int[] A, int n){
		int sum = 0;		// Calculate sum of the elements in array
		for(int i=0; i
  
   = 0){		// 选择A[j-1]的情况，更新总和为i-A[j-1]，也更新数组长度为j-1
					part[i][j] = part[i][j] || part[i-A[j-1]][j-1];
				}
			}
		}
		return part[sum/2][n];
	}
	
}

  

http://www.geeksforgeeks.org/dynamic-programming-set-18-partition-problem/