Cod sursa(job #3226304)
Utilizator | Costea Diana Stefania Dia3141 | Data | 20 aprilie 2024 21:06:13 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.45 kb |
#include <fstream>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int dp[10005],sol,n,G,p,g;
int main()
{
cin>>n>>G;
for(int i=1;i<=G;i++)
dp[i]=-1;
for(int i=1;i<=n;i++){
cin>>g>>p;
for(int j=G-g;j>=0;j--)
if(dp[j]!=-1)
dp[j+g]=max(dp[j]+p,dp[j+g]);
}
for(int i=1;i<=G;i++)
sol=max(sol,dp[i]);
cout<<sol;
return 0;
}