Cod sursa(job #1089721)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 21 ianuarie 2014 21:27:34
Problema Problema rucsacului Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>

using namespace std;

int w[5005], p[5005], v0[10005],v1[10005];

int n,gmax,i,j,Max;

int main() {
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    f>>n>>gmax;
    for(i=1;i<=n;i++)
        f>>w[i]>>p[i];
    v0[w[1]]=p[1];
    for(i=2;i<=n;i++) {
        for(j=0;j<=gmax;j++)
            if(w[i]<=j)
                v1[j] = max(v0[j],v0[j-w[i]]+p[i]);\
            else
                v1[j]=v0[j];
        for(j=0;j<=gmax;j++)
            v0[j]=v1[j];
    }
    for(i=0;i<=gmax;i++)
        if(v1[i]>Max)
            Max=v1[i];
    g<<Max<<"\n";
    return 0;
}