Împărţirea unei mulţimi în 2 submulţimi de sume cât mai apropiate

[•Mitza444]

Buna!!!Ma puteti ajuta cu niste indicatii de rezolvare la problema urmatoare:

La sfarsitul noptii de Craciun, Mosul a poposit la bradul a doi frati, unde si-a golit sacul. Cand s-au trezit, fratii au intrat intr-o mare dilema: cum isi vor imparti ei cadourile mosului? Stiind ca fiecare cadou are o valoare (cuprinsa intre 1 si 100 inclusiv) si ca sunt maxim 100 de cadouri scrieti un program care sa determine sumele cadourilor fratilor, precum si modul de impartire, astfel incat sumele obtinute sa fie cele mai apropiate posibil.

Date de intrare:
In fisierul CADOURI.IN se gasesc informaţiile referitoare la cadouri: pe prima linie numarul total de cadouri, pe urmatoarea linie valorile lor.

Date de iesire: In fişierul CADOURI.OUT trebuie scrise doua sume care sunt cele mai apropiate corespunzătoare unei impartiri a cadourilor, pe a doua linie valorile corespunzătoare cadourilor care însumează prima suma găsită, pe a treia linie, valorile corespunzătoare cadourilor care însumează a doua suma găsită.
Exemplu:

CADOURI.IN
7
28 7 11 8 9 7 27

CADOURI.OUT
48 49
28 11 9
7 8 7 27

[•scipianus]

Problema se rezolva cu programare dinamica (problema rusacului). Sa presupunem ca avem suma totala a valorilor cadourilor egala cu S (S va fi maxim 10.000). Dupa asta facem problema rucsacului,adica vom incerca sa vedem care este cea mai mare suma <= S/2 care poate fi obtinuta si astfel am gasit solutia,pentru ca restul sumei pana la S va fi suma obtinuta pentru al doilea copil si intrucat prima este maxima pana in S/2 atunci diferenta dintre cele doua va fi minima   Numarul de iteratii va fi (S/2)*N , unde N e numarul de cadouri , deci cam 500.000 maxim 

[•pauldb]

http://infoarena.ro/problema/jocul

Si exemplul e acelasi.

[•Mitza444]

Am facut cum mi-a sugerat scipianus cu problema rucsacului si merge tot inafara de ultimul test la care iau TLE.Ce optimizare pot sa-i mai fac??Am incercat citirea si scriere si cu fstream si cu cstdio aceealasi lucru TLE  : http://infoarena.ro/job_detail/670732
P.S.:Cum as putea face ca sa afisez si din ce numere este formata fiecare suma ca si in exemplu ?? (la jocul se cerea numai cele doua sume)

Cod:

#include<fstream>
using namespace std;
int G[1001],S;
int D[2][100002],s1,s2;
int main(){
ifstream f("jocul.in");
int n,i,j;
int l=0;
f>>n;
for(i=1;i<=n;i++){
f>>G[i];
S+=G[i];
}
for(i=1;i<=n;i++,l=1-l){
for(j=0;j<=S/2;j++){
D[1-l][j] = D[l][j];
if(j>=G[i])
D[1-l][j]=max(D[1-l][j],D[l][j-G[i]]+G[i]);
}
}
s1=D[l][S/2];
s2=S-D[l][S/2];
ofstream g("jocul.out");
g<<min(s1,s2)<<" "<<max(s1,s2)<<"\n";
return 0;
}

[•pauldb]

Poti face folosind o singura linie pentru dinamica si facand for-ul din mijloc descrescator.

[•Mitza444]

Nu m-am prins ca mergea cu o sigura linie 
Mersi mult

O ultima intrebare : Cum as putea sa retin si numere din care e formata fiecare suma?? (48=28+11+9 si 49=7+8+7+27)

[•pauldb]

Cel mai simplu este sa calculezi o informatie suplimentara b[ i ][ j ] = 0 / 1 daca pe D[ i ][ j ] l-ai calculat din D[ i-1 ][ j ] sau D[ i-1 ][ j-G[ i ] ].

E mai greu folosind spatiu liniar.