-1

My task is:

You have N items that weight is s1, s2... sN. Program has to divide items into two groups so that item weight would be as much similar as possible.

I found a great explanation how to solve this problem(Author: 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;
}

But the problem is that I also need to print these both groups of numbers on screen, while on this code I will get only minimum difference.

I would really appreciate your help, Thanks!

MCTG
  • 65
  • 11
  • 2
    `#include ` - [Don't do this.](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h). Include the proper header files. – PaulMcKenzie Apr 09 '18 at 09:29
  • This code was taken from a website, I fixed that – MCTG Apr 09 '18 at 09:32
  • 1
    So you just need to track the complete recursion path alongside the running total. You can replace the integer sum with a value type to do this (you only need 1 bit per level to track which branch you took) if `operator<` still only compares the running total, but you still return the whole winning path object. – Useless Apr 09 '18 at 09:39
  • Just a note, the above algorithm is very slow, with a runtime of O(2^n). The better way would be to just run a binary knapsack algorithm with target sum being half of the total sum. – eesiraed Apr 10 '18 at 00:44

1 Answers1

0

Did you need some thing like this:

#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;
}
Siro
  • 1
  • 1