Programowanie dynamiczne

Witam,
Mam problem z dwoma zadaniami z programowania dynamicznego. Prosze was o pomoc w dobraniu metody rozwiazania tych zadan, koniecznie optymalnej bo taka jest wymagana (wrzucam je na platforme do sprawdzenia).
Oto one:
http://scr.hu/2kgz/egkct
http://scr.hu/2kgz/6afom
Z gory bardzo dziekuje jezeli ktos by dal jakas rade lub pomysl tylko tego potrzebuje bo potem i tak sam musze to zrozumiec i rozwiazac. Po prostu nie mam zadnego pomyslu poza sprawdzeniem wszystkich mozliwosci dla tego zadania bursztyn a dla drugiego zadania moje rozwiazanie nie wchodzi na maksa bo wyrzuca zle wartosci takze licze na wasza pomoc.

Pomysł na zadanie drugie:
1. Sumę wszystkich wyrazów dzielisz przez dwa(dzielisz dorobek na 2 osoby ). Wynik da Ci wartość idealną do jakiej ma dążyć X i Y.
2. Według mnie, aby obie liczby były możliwie jak najbliżej siebie, czyli podział był jak najbardziej sprawiedliwy musisz zacząć przydzielać liczby od największej do najmniejszej.
3. Pamiętaj, że młodszy brat nie może dostać więcej niż wynik z punktu 1.

Dalsza optymalizacja należy do Ciebie ;)

Założyłeś 2 raz ten sam temat:
[href="http://cpp0x.pl/forum/temat/?id=21568"]

Zalozylem jeszcze raz poniewaz odnioslem wrazenie ze powodem przeniesienia bylo zle sformulowanie problemu, tutaj tego bledu nie popelnie.
Bezprzewodowy dzieki za propozycje ale wlasnie tak sprobowalem to rozwiazac.

Oto moj kod(niestety dostaje za niego 78/100 punktow) :


#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector < long long > tab;



int main()
{
 ios_base::sync_with_stdio(0);



int  n;
 cin >> n;
 int tab1 [n+1];
 int pom;

 for (int i=0; i<n;++i)
 {
     cin >> pom;
     tab.push_back(pom);
 }

 sort( tab.begin(), tab.end() );


  for (int i=0; i<n;++i)
 {
     tab1= tab[n-i-1];
 }



 int x=0;
 int y=0;

 for (int i=0; i<n ;++i)
 {

     if (x<=y)
     {
         x=x+tab1;
     }

     else if (x>y)
     {
         y=y+tab1;
     }
 }

 cout << max (x,y) << " " << min (x,y) << endl;


 return 0;
}

Twój kod robi trochę inaczej niż, to co podał BezPrzewodowy

1. Najpierw musisz założyć wynik maksymalny, czyli sumujesz wszystkie elementy, a następnie dzielisz na 2
2. Sortujesz tablice od największej do najmniejszej
3. Dodajesz po kolei elementy od największej, ale tylko do jednego syna, nie przekraczając wcześniej założonego maksimum.

Przykład 1 :
5 7 2 4 6 8
maksimum = 32/2 = 16
sort -> 8 7 6 5 4 2

wynik końcowy:
syn1 = 8 + 7 = 15 (dodanie 6, 5, 4 lub 2 - przekroczenie maksimum = 16)
syn2 = 6 + 5 + 4 + 2 = 17 (tego w programie liczyć nie trzeba)
rozbieżność  = 2

---------------------------
Przykład 2 :
5 7 1 5 6 8
maksimum = 32/2 = 16
sort -> 8 7 6 5 5 1

wynik końcowy:
syn1 = 8 + 7 + 1 = 16 (dodanie 6, 5 lub 5  - przekroczenie maksimum = 16)
syn2 = 6 + 5 + 5 = 16
rozbieżność  = 0

Wynik awansowal z 78 do 89 , cale skrzydlo weszlo ale dalej to nie 100, licze ze ktos jeszcze znajdzie jakis blad.

Oto moj kod po zmianach:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector < long long > tab;



int main()
{
 ios_base::sync_with_stdio(0);

int max1=0;

int  n;
 cin >> n;
 int tab1 [n+1];
 int pom;

 for (int i=0; i<n;++i)
 {
     cin >> pom;
     tab.push_back(pom);
     max1=max1+pom;
 }

 sort( tab.begin(), tab.end() );


  for (int i=0; i<n;++i)
 {
     tab1= tab[n-i-1];
 }
int max2;
max2=max1/2;

 int x=0;
 int y=0;

 for (int i=0; i<n ;++i)
 {
    if (x+tab1>max2)
    {
        continue;
    }
    else
    {
        x=x+tab1;
    }
 }
y=max1-x;

 cout << max (x,y) << " " << min (x,y) << endl;


 return 0;
}

Jeśli masz chęci, to spróbuj zrobić tak jak opisałem w poprzednim temacie, czy jest wydajniejszy, nie mam bladego pojęcia

Nie wiem czego oczekują od Ciebie dokładnie, ale:
- nie potrzebujesz już funkcji max() i min(), bo z góry założyłeś, że X nie możesz przekroczyć Twojego max2, czyli to on jest młodszym synem.
- Możesz posegregować wartości od razu malejąco
- Możesz użyć metody qsort, która jest szybsza

Nie wiem po co stworzona jest tab1 , tu może być moja niewiedza.