C++分区算法

Question

我的任务是：

您有 N 个项目，其重量为 s1、s2...锡。程序必须将项目分为两组，以便项目重量尽可能相似。

我找到了一个很好的解释如何解决这个问题(作者：Abhiraj Smit(：

// A Recursive C program to solve minimum sum partition
// problem.
#include <stdio.h>
using namespace std;
// Function to find the minimum sum
int findMinRec(int arr[], int i, int sumCalculated, int sumTotal)
{
    // If we have reached last element.  Sum of one
    // subset is sumCalculated, sum of other subset is
    // sumTotal-sumCalculated.  Return absolute difference
    // of two sums.
    if (i==0)
        return abs((sumTotal-sumCalculated) - sumCalculated);

    // For every item arr[i], we have two choices
    // (1) We do not include it first set
    // (2) We include it in first set
    // We return minimum of two choices
    return min(findMinRec(arr, i-1, sumCalculated+arr[i-1], sumTotal),
               findMinRec(arr, i-1, sumCalculated, sumTotal));
}
// Returns minimum possible difference between sums
// of two subsets
int findMin(int arr[], int n)
{
    // Compute total sum of elements
    int sumTotal = 0;
    for (int i=0; i<n; i++)
        sumTotal += arr[i];
    // Compute result using recursive function
    return findMinRec(arr, n, 0, sumTotal);
}
// Driver program to test above function
int main()
{
    int arr[] = {3, 1, 4, 2, 2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "The minimum difference between two sets is "
         << findMin(arr, n);
    return 0;
}

但问题是我还需要在屏幕上打印这两组数字，而在此代码上我只会得到最小的差异。

我真的很感激你的帮助，谢谢！

Answer 1

你需要这样的东西吗：

#include<iostream>
#include<math.h>
using namespace std;
int lim, ans = 0, k, min1 = INT_MAX;
int a[] = { 3, 1, 4, 2, 2, 1 };
int n = sizeof(a) / sizeof(a[0]);
int bit;
int main()
{
    lim = 1 << n;
    for (int i = 1; i < lim; i++)
    {
        k = 0;
        for (int j = 1; j < (1 << n); (j = j << 1))
        {
            if (i&j)
                ans += a[k];
            else ans -= a[k];
            k++;
        }
        k = 0;
        if (min1 > abs(ans)) {
            min1 = abs(ans);
            bit = i;
        }
        ans = 0;
    }
    cout << min1 << endl;
    cout << bit << endl;
    int temp = 1;

    for (int i = 0; i < n; i++) {
        if (bit&temp) cout << a[i] << " ";
        temp = temp << 1;
    }
    cout << endl;
    temp = 1;
    for (int i = 0; i < n; i++) {
        if (!(bit&temp)) cout << a[i] << " ";
        temp = temp << 1;
    }
    return 0;
}