Given one can change the sign of numbers, find Minimum Sum of array

this problem can be changed to a knap-sack problem

consider this problem:

you are given n integers, and obviously, you can calculate the sum of these number, suppose it is S

you are now required to choose a set of numbers from them, and aims to sum these chosen numbers to be as close to S/2 as possible

this can be done using a DP algorithm which is very similar to knap-sack problem

can you do it now? :)

this post is just a hint, if you need more help, i can give more details

I was irritated by the other answers, saying something about knap-sack.

Knap-Sack means you have a target S and a list of weights A and you are looking for a subset of A that sums up to S.

To me it looks more like makespan scheduling where you have two machines and have to assign all the jobs to them such that the makespan is minimal.

So you can think about it as two stacks and you try to minimize the difference of their height.

An 3/2-approximation algorithm is this:

• Sort the list (max to min)
• for each object, lay it on the stack with the lowest height

You get your approximation by turning the sign of all objects on the smaller stack negative summing the numbers up. (i.e. computing the absolute difference of the both stacks)

If you search for minimal makespan scheduling, you can find a PTAS and an exact algorithm that needs exponential time in the length of the list.

Sorting won't work here because this cannot be solved by Greedy approach just like in 0-1 Knapsack. You can think this way, every element in the array has 2 choices either be negative or positive. You can develop a recursive solution by either selecting a number (one branch) or not selecting it (the other branch)

Here's an implementation of what I was saying. The code can be improved in several ways. Sorry if it has very less comments. I am running short of time.

#include "iostream"#include <algorithm>using namespace std;int *arr,*flag,mini=1000; int* sol; //Flag array is used to see which all elements are selected in that call of the functionvoid find_difference(int* arr,int* flag,int n,int current,int *sol){if(current==n)return;int sum0=0, sum1=0,entered=0;flag[current]=1;              //Selecting the current indexed numberfor (int i = 0; i < n; ++i){    if(flag[i]==0)    {        sum0=sum0+arr[i];    }    else    {        sum1=sum1+arr[i];    }}    if(abs(sum0-sum1)<mini)    {        mini=abs(sum0-sum1);        for (int j = 0; j < n; ++j)        {            sol[j]=flag[j];    //Remebering the optimal solution        }    }find_difference(arr,flag,n,current+1,sol);  //Moving to the next index to perform the same operation (selecting or not selecting it)flag[current]=0;                 // Not selecting itfor (int i = 0; i < n; ++i){    if(flag[i]==0)    {        sum0=sum0+arr[i];    }    else    {        sum1=sum1+arr[i];    }}    if(abs(sum0-sum1) < mini)    {        mini=abs(sum0-sum1);        for (int j = 0; j < n; ++j)        {            sol[j]=flag[j];        }    }find_difference(arr,flag,n,current+1,sol);}int main(int argc, char const *argv[]){int n;cout<<"Enter size: ";cin>>n;cout<<"Enter the numbers: "arr= new int[n];flag= new int[n];sol= new int[n];for (int i = 0; i < n; ++i){    cin>>arr[i];    flag[i]=0;    sol[i]=0;}find_difference(arr,flag,n,0,sol);cout<<"Min = "<<mini<<endl;cout<<"One set is: ";for (int i = 0; i < n; ++i){    if (sol[i]==1)    {        cout<<arr[i]<<" ";    }}cout<<"\nOther set is: ";for (int i = 0; i < n; ++i){    if (sol[i]==0)    {        cout<<arr[i]<<" ";    }}cout<<"\n";return 0;}