Задача Натпревар (тест натпревар март 2012)

Проблемот е knapsack(максимален збир) со 1 повторување...
Има сложеност N*M... Незнам каде се буниш за да ти објаснам...

Moeto resenie e N^3

Si raboti

filip_bujaroski wrote:Moeto resenie e N^3
Si raboti

N^3 ти е решението?! Како?

Greshka sum bil(vasja mi kaza deka e N^3, ama povekje e )

(N^2)*suma od jacinite na site natprevaruvaci

Така може

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <math.h>

using namespace std;

int main()
{
    int n,a=0,b=0,a1=0,b1=0,i,j;
    cin>>n;
      vector<int> natprevaruvaci;
      for(i=0;i<n;i++)
      {
            cin>>a;
            natprevaruvaci.push_back(a);
            b+=a;
      }
      bool dp[70][5050];
      memset(dp,false,sizeof(dp));
      dp[0][0]=true;
    for(int k=0;k<n;k++)
    {
            for(i=n-1;i>=0;i--)
      {
            for(j=0;j<b;j++)
            {
                  if(dp[i][j]==true)
                  {
                        dp[i+1][j+natprevaruvaci[k]]=true;
                        //cout><<i<<" "<<j><<" "<<natprevaruvaci[k]><<endl;
                  }
            }
      }

}
    int x=0,y=0;
    int r1,r2;

for(i=0;i<b;i++)
    {
          if(dp[n/2][i])
          {
                x=b-i;
                y=b-x;
                if(fabs(x-y)><fabs(r1-r2))
                {
                      r1=x;
                      r2=y;
                }
          }
    }
    cout><<min(r1,r2)<<" "<<max(r1,r2)><<endl;

return 0;
}

Ova mi e kodot na zadacata
go testirav na 4 razlicni primeri od mendo, i lokalno si raboti super(ne se prvite 4, random 4

)
Na mendo koga kje pratam mi dava pogresen rezultat za site...
Shto moze da e rabotata?

filip_bujaroski wrote:Ova mi e kodot na zadacata
go testirav na 4 razlicni primeri od mendo, i lokalno si raboti super(ne se prvite 4, random 4 )
Na mendo koga kje pratam mi dava pogresen rezultat za site...
Shto moze da e rabotata?

Стави

This message was edited 1 time. Last update was at 04/04/2012 00:27:52

Jasno

Pomina

filip_bujaroski wrote:Jasno

Pomina

Бујо, срамота бе, уште не си научил да си ги иницијализираш променливите пред да ги користиш

obi1kenobi wrote:

filip_bujaroski wrote:Jasno

Pomina

Бујо, срамота бе, уште не си научил да си ги иницијализираш променливите пред да ги користиш

Abe dobro

Koi se shansite da se pogodat vo range 5000 edna od druga koga kje im dades random vrednost od -2miljardi do +2miljardi

Ama jebiga, na serverot verojatno isto gi inicijalizira, ne na random

Tezok moj zivot