Cod sursa(job #2913056)
| Utilizator | Data | 12 iulie 2022 14:28:18 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.53 kb |
#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int g[10005],pr[10005],dp[10005];
int main()
{
long long maxi=0,n,G;
in>>n>>G;
for(int i=1;i<=n;i++)
in>>g[i]>>pr[i];
dp[0]=0;
for(int i=1;i<=n;i++)
for(int j=G;j>=0;j--)
{
if(dp[j]+pr[i]>=dp[g[i]+j] && j+g[i]<=G)
dp[g[i]+j]=dp[j]+pr[i];
}
for(int j=G;j>=1;j--)
if(maxi<dp[j])
maxi=dp[j];
out<<maxi;
return 0;
}
