Cod sursa(job #2669973)
Utilizator | Cosmina Stefania stephenie | Data | 8 noiembrie 2020 16:09:52 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.64 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int v[5001],dp[10001];
int n,i,j,maxx;
int g,gmax,p;
int main()
{
fin>>n>>gmax;
dp[0]=0;
for(i=1;i<=gmax;i++)
dp[i]=-1;
for(j=1;j<=n;j++)
{
fin>>g>>p;
for(i=gmax-g;i>=0;i--)
{
if(dp[i]!=-1 && dp[i]+p>dp[i+g])
{
dp[i+g]=dp[i]+p;
}
}
}
for(i=1;i<=gmax;i++)
if(dp[i]>maxx)
maxx=dp[i];
fout<<maxx;
return 0;
}