http://mendo.mk/jforum/posts/list/12.page JForum - http://www.jforum.net http://mendo.mk/algoritmi/Task.do?competition=150&id=255.

Nemie jasna zosto pominuva so greedy resenie a so DP(dinamicko programiranje) resenie ne pominuva.

Ova e resenieto za koe pominuva

[code]#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {

int n;

cin >> n;

int a[n];

for (int i = 0 ; i < n ; i++){
cin >> a[i];
}

sort(a, a + n);

int sum1 = a[n - 1] , sum2 = a[n - 2];



for (int i = n - 3 ; i >= 0 ; i--){
if (sum1 < sum2){
sum1 += a[i];
}else {
sum2 += a[i];
}
}

cout << min(sum1, sum2) << " " << max(sum1, sum2) << endl;

return 0;
}[/code]

a ova e resenieto kade sto pagja na runtime
[code]#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>

using namespace std;

int findMin(int arr[], int n, int sum){

bool dp[n + 1][sum + 1];

for (int i = 0; i <= n; i++)
dp[i][0] = true;

for (int i = 1; i <= sum; i++)
dp[0][i] = false;

for (int i = 1; i <= n; i++){
for (int j = 1; j <= sum; j++){

dp[i][j] = dp[i - 1][j];

if (arr[i - 1] <= j)
dp[i][j] |= dp[i - 1][j - arr[i - 1]];
}
}

int diff = INT_MAX;

for (int j = sum / 2; j >= 0; j--){

if (dp[n][j]){
diff = sum - 2 * j;
break;
}
}

return diff;
}

int main() {

int n, sum = 0;

cin >> n;

int a[n];

for (int i = 0 ; i < n ; i++){
cin >> a[i];
sum += a[i];
}

int minVal = findMin(a, n, sum);

int large = (sum + minVal) / 2;
int small = large - minVal;

cout << small << " " << large << endl;

return 0;
}[/code]

Prasanjeto mi bese zosto zadacata e napravena samo da se resava so greedy approach a ne kako sto treba.
Ova go sogledav koga vidov deka vo zadacata pisuva da se najdi optimalnoto resenie kade sto ke ima minimalna razlika pomegju dvete grupi od nakiti no za dolniot slucaj ako odime po greedy resenieto(za koe pominuva 10/10) ke bide
14 12 10 20 22 ====> greedy (22 + 12 + 10 = 44 i 20 + 14 = 34 sto ke ispecati (34 44) no treba da bide (10 + 12 + 14 = 36 20 + 22 = 42 ) sto znaci pagja na ovoj slucaj no 10/10 pominuva na od MENDO slucaite sto ne mie jasno ....)
dodeka so DP resenieto si pecati najoptimalnoto grupiranje (36 42) no pagja na runtime za 4 slucai sto ne mie jasno zosto vaka e postavena zadacata.]]> http://mendo.mk/jforum/posts/preList/492/3191.page http://mendo.mk/jforum/posts/preList/492/3191.page GMT За да се надмине овој проблем, клучно е да се увиди кои податоци [b]не[/b] треба да ги чуваме. За да пресметаме произволен елемент од матрицата dp[i][j], нас ни требаат само вредностите од редот i-1, сите останати редици не ни играат улога, од што може да се заклучи дека во еден момент нам ни е потребно да чуваме само [b]2[/b] редици од матрицата (претходната редица и таа што во сегашниот момент ја пресметуваме), што многу ни ја намалува меморијата.]]> http://mendo.mk/jforum/posts/preList/492/3192.page http://mendo.mk/jforum/posts/preList/492/3192.page GMT