11/22 - Greedy

Se dă un şir de n nr. nat. Folosind un algoritm Greedy, partiţionaţi şirul în două submulţimi care au proprietatea că diferenţa dintre sumele elementelor este minimă.

#include<iostream>
#include<fstream>
using namespace std;
int n,a[100];
void citire()
{int i;
ifstream f("date");
f>>n;
for(i=0;i<n;i++)
    f>>a[i];
}

void afisare(int x[],int n)
{int i;
for(i=0;i<n;i++)
    cout<<x[i]<<" ";
cout<<endl;
}

int main()
{int i,j=0,k=0,p=0,v[100],s=0,b[100],c[100],ss=0;
citire();
sort(a,n+a);
for(i=0;i<n;i++)
    s=s+a[i];
for(i=n-1;i>=0;i--)
{    if(ss+a[i]<=s/2)
        {b[k]=a[i];
        ss=ss+b[k];
        k++;}
    else
        {v[p]=i;
        p++;}
}
for(i=0;i<p;i++)
    {c[j]=a[v[i]];
    j++;}
afisare(b,k);
cout<<"Suma "<<ss<<endl;
afisare(c,j);
cout<<"Suma "<<s-ss<<endl;
cout<<"Diferenta "<<abs(s-ss-ss);
}

Fişier

9
2 5 7 1 9 10 6 4 3