Cod sursa(job #1714167)

Utilizator Vlad1111Sbengheci Vlad-Andrei Vlad1111 Data 7 iunie 2016 18:17:22
Problema Problema rucsacului Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <cstdio>

using namespace std;

int a[10010],n,g,gr[5010],pr[5010];

void citire()
{
    scanf("%d %d",&n,&g);

    for(int i=1;i<=n;i++)
        scanf("%d %d",&gr[i],&pr[i]);
}

void rez()
{
    a[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=g;j>=gr[i];j--)
            if(a[j-gr[i]]!=0)
                a[j]=max(a[j-gr[i]]+pr[i],a[j]);
    }
//
////    while(a[g]==0)
////        g--;
////    printf("%d",a[g]-1);
//
//for(int i=0;i<=g;i++)
//    cout<<a[i]<<endl;

    int m=-1;
    for(int i=1;i<=g;i++)
        m=max(a[i],m);

    printf("%d",m-1);
}


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

    citire();

    rez();

    return 0;
}