[0, 1, 5, 6]。你会声称{0, 5}和{1, 6}，但最好的答案实际上是{0, 1, 5}和{6}。#include<bits/stdc++.h>
#define rep(i,_n) for(int i=0;i<_n;i++)
using namespace std;
#define MXN 55
int a[MXN];
int main() {
//code
int t,n,c;
cin>>t;
while(t--){
cin>>n;
rep(i,n) cin>>a[i];
sort(a, a+n);
reverse(a, a+n);
ll sum1 = 0, sum2 = 0;
rep(i,n){
cout<<a[i]<<endl;
if(sum1<=sum2)
sum1 += a[i];
else
sum2 += a[i];
}
cout<<abs(sum1-sum2)<<endl;
}
return 0;
}
测试用例：
1
8
16 14 13 13 12 10 9 3
Wrong Ans: 6
16 13 10 9
14 13 12 3
Correct Ans: 0
16 13 13 3
14 12 10 9
我的代码（与this相同）：
#include<bits/stdc++.h>
#define rep(i,_n) for(int i=0;i<_n;i++)
using namespace std;
#define MXN 55
int arr[MXN];
int dp[MXN][MXN*MXN];
int main() {
//code
int t,N,c;
cin>>t;
while(t--){
rep(i,MXN) fill(dp[i], dp[i]+MXN*MXN, 0);
cin>>N;
rep(i,N) cin>>arr[i];
int sum = accumulate(arr, arr+N, 0);
dp[0][0] = 1;
for(int i=1; i<=N; i++)
for(int j=sum; j>=0; j--)
dp[i][j] |= (dp[i-1][j] | (j>=arr[i-1] ? dp[i-1][j-arr[i-1]] : 0));
int res = sum;
for(int i=0; i<=sum/2; i++)
if(dp[N][i]) res = min(res, abs(i - (sum-i)));
cout<<res<<endl;
}
return 0;
}
也许你在谈论这个。
我使用了Meet in the Middle方法来完成。这是一种优化技术，它通过将数组分成两部分，然后生成子集来工作。
代码，请随时提问。
class Solution{
public:
void generate(vector<int> &arr, int curr, int n, int sum, vector<vector<pair<int,vector<int>>>> &store, vector<int> build){
if(curr==n){
int sz=build.size();
store[sz].push_back({sum,build});
return;
}
build.push_back(curr);
generate(arr,curr+1,n,sum+arr[curr],store,build);
build.pop_back();
generate(arr,curr+1,n,sum,store,build);
}
static bool cmp(pair<int,vector<int>> &p1, pair<int,vector<int>> &p2){
return p1.first<p2.first;
}
int BINRY_SRCH(vector<pair<int,vector<int>>> &arr, int target){
int res=-1;
int low=0;
int high=arr.size()-1;
while(low<=high){
int mid=(low+high)/2;
if(arr[mid].first>=target){
res=mid;
high=mid-1;
}
else{
low=mid+1;
}
}
return res;
}
vector<vector<int>> minDifference(vector<int>& arr, int n){
int extra=(n%2!=0);
vector<vector<pair<int,vector<int>>>> part1(n/2+1+extra);
vector<vector<pair<int,vector<int>>>> part2(n/2+1);
generate(arr,0,n/2+extra,0,part1,{});
generate(arr,n/2+extra,n,0,part2,{});
for(auto &c: part2){
sort(c.begin(),c.end(),cmp);
}
vector<vector<int>> res(2);
int diff=INT_MAX;
int sum=accumulate(arr.begin(),arr.end(),0);
for(int ele=1;ele<=n/2+extra;ele++){ // making a single subset
vector<pair<int,vector<int>>> P1=part1[ele];
vector<pair<int,vector<int>>> P2=part2[n/2+extra-ele];
for(auto x: P1){
int index=BINRY_SRCH(P2,sum/2-x.first);
if(index!=-1){
int subset1_Sum=x.first+P2[index].first;
int subset2_Sum=sum-subset1_Sum;
if(abs(subset1_Sum-subset2_Sum)<diff){
diff=abs(subset1_Sum-subset2_Sum);
vector<int> subset1=x.second;
for(auto c: P2[index].second){
subset1.push_back(c);
}
res[0]=subset1;
}
}
if(index>0){
index--;
int subset1_Sum=x.first+P2[index].first;
int subset2_Sum=sum-subset1_Sum;
if(abs(subset1_Sum-subset2_Sum)<diff){
diff=abs(subset1_Sum-subset2_Sum);
vector<int> subset1=x.second;
for(auto c: P2[index].second){
subset1.push_back(c);
}
res[0]=subset1;
}
}
}
}
vector<bool> vis(n,false);
for(int i=0;i<res[0].size();i++){
vis[res[0][i]]=true;
res[0][i]=arr[res[0][i]];
}
vector<int> subset2;
for(int i=0;i<n;i++){
if(vis[i]==false){
subset2.push_back(arr[i]);
}
}
res[1]=subset2;
// for(auto c: res[0]){
// cout<<c<<" ";
// }
// cout<<endl;
// for(auto c: res[1]){
// cout<<c<<" ";
// }
// cout<<endl;
return res;
}
};
代码由RAINX，ABHIJIT ROY和NIT AGARTALA编写
递归方法是从数组的所有值生成所有可能的和，并检查哪个解决方案最优。 要生成总和，我们要么将第i个项目包含在集合1中，要么不包含，即包含在集合2中。
时间复杂度为O(n*sum)，对于时间和空间都是如此。
public class MinimumSubsetSum {
static int dp[][];
public static int minDiffSubsets(int arr[], int i, int calculatedSum, int totalSum) {
if(dp[i][calculatedSum] != -1) return dp[i][calculatedSum];
/**
* If i=0, then the sum of one subset has been calculated as we have reached the last
* element. The sum of another subset is totalSum - calculated sum. We need to return the
* difference between them.
*/
if(i == 0) {
return Math.abs((totalSum - calculatedSum) - calculatedSum);
}
//Including the ith element
int iElementIncluded = minDiffSubsets(arr, i-1, arr[i-1] + calculatedSum,
totalSum);
//Excluding the ith element
int iElementExcluded = minDiffSubsets(arr, i-1, calculatedSum, totalSum);
int res = Math.min(iElementIncluded, iElementExcluded);
dp[i][calculatedSum] = res;
return res;
}
public static void util(int arr[]) {
int totalSum = 0;
int n = arr.length;
for(Integer e : arr) totalSum += e;
dp = new int[n+1][totalSum+1];
for(int i=0; i <= n; i++)
for(int j=0; j <= totalSum; j++)
dp[i][j] = -1;
int res = minDiffSubsets(arr, n, 0, totalSum);
System.out.println("The min difference between two subset is " + res);
}
public static void main(String[] args) {
util(new int[]{3, 1, 4, 2, 2, 1});
}
}
import itertools as it
def min_diff_sets(data):
"""
Parameters:
- `data`: input list.
Return:
- min diff between sum of numbers in two sets
"""
if len(data) == 1:
return data[0]
s = sum(data)
# `a` is list of all possible combinations of all possible lengths (from 1
# to len(data) )
a = []
for i in range(1, len(data)):
a.extend(list(it.combinations(data, i)))
# `b` is list of all possible pairs (combinations) of all elements from `a`
b = it.combinations(a, 2)
# `c` is going to be final correct list of combinations.
# Let's apply 2 filters:
# 1. leave only pairs where: sum of all elements == sum(data)
# 2. leave only pairs where: flat list from pairs == data
c = filter(lambda x: sum(x[0])+sum(x[1])==s, b)
c = filter(lambda x: sorted([i for sub in x for i in sub])==sorted(data), c)
# `res` = [min_diff_between_sum_of_numbers_in_two_sets,
# ((set_1), (set_2))
# ]
res = sorted([(abs(sum(i[0]) - sum(i[1])), i) for i in c],
key=lambda x: x[0])
return min([i[0] for i in res])
if __name__ == '__main__':
assert min_diff_sets([10, 10]) == 0, "1st example"
assert min_diff_sets([10]) == 10, "2nd example"
assert min_diff_sets([5, 8, 13, 27, 14]) == 3, "3rd example"
assert min_diff_sets([5, 5, 6, 5]) == 1, "4th example"
assert min_diff_sets([12, 30, 30, 32, 42, 49]) == 9, "5th example"
assert min_diff_sets([1, 1, 1, 3]) == 0, "6th example"
public int minDiffernce(int set[]) {
int sum = 0;
int n = set.length;
for(int i=0; i<n; i++)
sum+=set[i];
//finding half of total sum, because min difference can be at max 0, if one subset reaches half
int target = sum/2;
boolean[][] dp = new boolean[n+1][target+1];//2
for(int i = 0; i<=n; i++)
dp[i][0] = true;
for(int i= 1; i<=n; i++){
for(int j = 1; j<=target;j++){
if(set[i-1]>j) dp[i][j] = dp[i-1][j];
else dp[i][j] = dp[i-1][j] || dp[i-1][j-set[i-1]];
}
}
// we now find the max sum possible starting from target
int firstPart = 0;
for(int j = target; j>=0; j--){
if(dp[n][j] == true) {
firstPart = j; break;
}
}
int secondPart = sum - firstPart;
return Math.abs(firstPart - secondPart);
}
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int n;
cin>>n;
int arr[n],sum=0;
for(int i=1;i<=n;i++)
cin>>arr[i],sum+=arr[i];
int temp=sum/2;
int dp[n+1][temp+2];
for(int i=0;i<=n;i++)
{
for(int j=0;j<=temp;j++)
{
if(i==0 || j==0)
dp[i][j]=0;
else if(arr[i]<=j)
dp[i][j]=max(dp[i-1][j],dp[i-1][j-arr[i]]+arr[i]);
else
{
dp[i][j]=dp[i-1][j];
}
}
}
cout<<sum-2*dp[n][temp]<<endl;
}
这可以使用二叉搜索树（BST）来解决。
首先对数组进行排序，称为arr1
然后创建另一个数组arr2，其中包含arr1的最后一个元素（从arr1中删除此元素）
现在：重复步骤，直到不再发生交换。
示例Java代码：
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* Divide an array so that the difference between these 2 is min
*
* @author shaikhjamir
*
*/
public class DivideArrayForMinDiff {
/**
* Create 2 arrays and try to find the element from 2nd one so that diff is
* min than the current one
*/
private static int sum(List<Integer> arr) {
int total = 0;
for (int i = 0; i < arr.size(); i++) {
total += arr.get(i);
}
return total;
}
private static int diff(ArrayList<Integer> arr, ArrayList<Integer> arr2) {
int diff = sum(arr) - sum(arr2);
if (diff < 0)
diff = diff * -1;
return diff;
}
private static int MIN = Integer.MAX_VALUE;
private static int binarySearch(int low, int high, ArrayList<Integer> arr1, int arr2sum) {
if (low > high || low < 0)
return -1;
int mid = (low + high) / 2;
int midVal = arr1.get(mid);
int sum1 = sum(arr1);
int resultOfMoveOrg = (sum1 - midVal) - (arr2sum + midVal);
int resultOfMove = (sum1 - midVal) - (arr2sum + midVal);
if (resultOfMove < 0)
resultOfMove = resultOfMove * -1;
if (resultOfMove < MIN) {
// lets do the swap
return mid;
}
// this is positive number greater than min
// which mean we should move left
if (resultOfMoveOrg < 0) {
// 1,10, 19 ==> 30
// 100
// 20, 110 = -90
// 29, 111 = -83
return binarySearch(low, mid - 1, arr1, arr2sum);
} else {
// resultOfMoveOrg > 0
// 1,5,10, 15, 19, 20 => 70
// 21
// For 10
// 60, 31 it will be 29
// now if we move 1
// 71, 22 ==> 49
// but now if we move 20
// 50, 41 ==> 9
return binarySearch(mid + 1, high, arr1, arr2sum);
}
}
private static int findMin(ArrayList<Integer> arr1) {
ArrayList<Integer> list2 = new ArrayList<>(arr1.subList(arr1.size() - 1, arr1.size()));
arr1.remove(arr1.size() - 1);
while (true) {
int index = binarySearch(0, arr1.size(), arr1, sum(list2));
if (index != -1) {
int val = arr1.get(index);
arr1.remove(index);
list2.add(val);
Collections.sort(list2);
MIN = diff(arr1, list2);
} else {
// now try for arr2
int index2 = binarySearch(0, list2.size(), list2, sum(arr1));
if (index2 != -1) {
int val = list2.get(index2);
list2.remove(index2);
arr1.add(val);
Collections.sort(arr1);
MIN = diff(arr1, list2);
} else {
// no switch in both the cases
break;
}
}
}
System.out.println("MIN==>" + MIN);
System.out.println("arr1==>" + arr1 + ":" + sum(arr1));
System.out.println("list2==>" + list2 + ":" + sum(list2));
return 0;
}
public static void main(String args[]) {
ArrayList<Integer> org = new ArrayList<>();
org = new ArrayList<>();
org.add(1);
org.add(2);
org.add(3);
org.add(7);
org.add(8);
org.add(10);
findMin(org);
}
}
- 预期子集总和=所有元素的总和/2
- 对数组进行排序
- 从最后一个元素开始添加，直到总和刚好小于或刚好大于之前计算的预期子集总和。
- 现在从上一步中取出两个子集，它们给出了最小的差异。
- dvsakgec