Cod sursa(job #650335)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 17 decembrie 2011 21:20:18
Problema Problema rucsacului Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#define nmax 5010
#define gmax 10010

int dp[2][gmax];//dp[i][j] castigul maxim, daca consider doar primele i obiecte (o submultmie a lor), iar greutatea lor este j

int main(){ 
  int n,G;
  int g[nmax],p[nmax];
  freopen("rucsac.in","r",stdin);
  scanf("%d%d",&n,&G);
  int i,j;
  for(i=1;i<=n;i++)
     scanf("%d%d\n",&g[i],&p[i]);
//  dp[0][0]=0; oricum, practic totul e initializat cu zero........
  int aux,aux2;
  int indice=0;
  for(i=0;i<n;i++,indice=!indice)
    for(j=0;j<=G;j++){
      aux=j+g[i+1];
      if(aux<=G){
        aux2=dp[indice][j]+p[i+1];
        if((dp[!indice][aux])<aux2)
          dp[!indice][aux]=aux2;
      }
      if(dp[!indice][j]<dp[indice][j])dp[!indice][j]=dp[indice][j];
   }
  int max=-1;
  for(i=1;i<=gmax;i++){
     if(max<dp[indice][i])max=dp[indice][i];
  }

  freopen("rucsac.out","w",stdout);
  printf("%d\n",max);
return 0;
}