Cod sursa(job #913970)

Utilizator Sm3USmeu Rares Sm3U Data 13 martie 2013 21:01:46
Problema Problema rucsacului Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <cstdio>

#define max(a,b) ((a>b)?a:b)
#define nMax 5010
#define gMax 10010

using namespace std;

struct lucruri{
    int val;
    int g;
}a[nMax];

int n;
int g;
int s1[gMax];
int s2[gMax];

void citire(){
    scanf("%d %d", &n, &g);
    for(int i = 0; i < n; ++ i){
        scanf("%d %d", &a[i].g, &a[i].val);
    }
}

void copiere(){
    for(int i = 1; i <= g; ++ i){
        s1[i] = s2[i];
    }
}

void rez(){
    for(int i = 0; i < n; ++ i){
        for(int j = a[i].g; j <= g; ++ j){
            s2[j] = max(s1[j], a[i].val + s1[j - a[i].g]);
        }
        copiere();
    }
    printf("%d\n", s1[g]);
}

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

    citire();
    rez();

    return 0;
}