Cod sursa(job #2696141)

Utilizator YolloSteffSandor Stefan YolloSteff Data 15 ianuarie 2021 14:00:03
Problema Problema rucsacului Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>
#include <algorithm>

using namespace std;

struct eu
{
    int gr, val;
};
eu v[5001];
int sum[10001];
int main(){
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
	int i, n, gmax, s=0, j, maxx;
	cin >> n >> gmax;
	for(i=1;i<=n;i++)
    {
        cin >> v[i].gr >> v[i].val;
    }
    for(i=1;i<=n;i++)
    {
        for(j=gmax-v[i].gr; j>=0; j--)
        {
            if(sum[j]!=0||j==0)
                sum[j+v[i].gr]=max(sum[j+v[i].gr],sum[j]+v[i].val);
        }
    }
    maxx=-1;
    for(i=1;i<=gmax;i++)
        if(sum[i]>maxx)
            maxx=sum[i];
    cout << maxx;
	return 0;
}