LeetCode 416 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.

题解：此题为0-1背包问题，首先对数组元素求和，若和为奇数，直接返回false；若为偶数，则建立二维数组f[m][n+1],m为数组长，n为和的一半。

所以f[i][v]表示前i个放入一个和为v的背包可以获得的最大价值（这里价值的大小w[i]等于nums[i]的数值大小）。

则其状态转移方程便是：f[i][v]=max{ f[i-1][v], f[i-1][v-w[i]]+v[i] }。

最后判断f[m-1][n]是否等于n即可。

代码（Java）：

public boolean canPartition(int[] nums) {
		 int sum=0;
		 for(int i=0;i<nums.length;i++) sum+=nums[i];
		 if(sum%2==1) return false;
		 else{
			int m=nums.length;
			int n=sum/2;
			int []value=nums;
			int f[][]=new int[m][n+1];
		
			for(int i=nums[0];i<=n;i++){
				f[0][i]=value[0];
			}
			
			for(int i=1;i<m;i++){
				for(int j=nums[i];j<=n;j++){
					f[i][j]=Math.max(f[i-1][j], f[i-1][j-nums[i]]+value[i]);
				}
			}
			if(f[m-1][n]==n) return true;
			else return false;
		 }
		
	 }

最后

以上就是认真心情为你收集整理的LeetCode 416 Partition Equal Subset Sum的全部内容，希望文章能够帮你解决LeetCode 416 Partition Equal Subset Sum所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。