Cod sursa(job #652330)

Utilizator Smaug-Andrei C. Smaug- Data 24 decembrie 2011 00:26:48
Problema Problema rucsacului Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define MAXW 10010

int main(){

  freopen("rucsac.in", "r", stdin);
  freopen("rucsac.out", "w", stdout);

  int N, maxW, val, W, i, j;
  int *A, *B, *aux, MEM1[MAXW], MEM2[MAXW];

  A=MEM1; B=MEM2;
  memset(MEM1, 0, sizeof(MEM1));

  scanf("%d%d", &N, &maxW);

  for(i=1; i<=N; i++){
    scanf("%d%d", &W, &val);

    for(j=0; j<=maxW; j++){
      if(W > j)
	B[j]=A[j];
      else
	B[j]=max(A[j], A[j-W]+val);
    }

    aux=A; A=B; B=aux;

  }

  printf("%d\n", A[maxW]);

  return 0;

}