lintcode724. 最小划分

阳光穿透心脏的1/2处 2023-05-21 15:29 96阅读 0赞

给出一个正整数数组，写一个程序把这个整数数组分成S1跟S2两部分，使S1中的和跟S2中的和的差的绝对值最小。换句话讲，如果有一个一个整数数组 S 有 n 个数，如果Subset1有 m 个数，Subset2必须有 n-m 个数并且 abs(sum(Subset1) – sum(Subset2)) 应该最小

样例
    样例1
    
    输入: nums = [1, 6, 11, 5]
    输出: 1
    解释: 
    Subset1 = [1, 5, 6]，和是12
    Subset2 = [11]，和是11
    abs(11 - 12) = 1
    样例2
    
    输入: nums = [1, 2, 3, 4]
    输出: 0
    解释: 
    Subset1 = [1, 4], 和是 5
    Subset2 = [2, 3], 和是5   
    abs(5 - 5) = 0

看成01背包，target值为数组和的一半。找出小于一半的最大数组和，然后用总数组和减去小于一半的最大数组和得到大于一半的最大数组和，这时候再用大于一半的数组和减去小于一半的数组和，就是该数组的的最小划分

class Solution {
        
    public:
        /**
         * @param nums: the given array
         * @return: the minimum difference between their sums 
         */
        int findMin(vector<int> &nums) {
        
            // write your code here
            if(nums.size()==0) return 0;
            int sum=0;
            for (auto i : nums) {
        
                sum+=i;
            }
            int half=sum/2;
            vector<bool> dp(half+1,false);
            dp[0]=true;
            for (int i = 0; i < nums.size(); i++) {
        
                for(int j = half; j >= nums[i];j--)
                {
        
                    if(dp[j-nums[i]]) dp[j]=true;
                }
            }
            for (int i = half; i >= 0; i--) {
        
                if(dp[i])
                {
        
                    return abs(sum-i-i);
                }
            }
            
        }
    };