Cod sursa(job #2467990)
| Utilizator | Data | 5 octombrie 2019 11:20:18 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.51 kb |
#include <bits/stdc++.h>
#define NM 5005
#define GM 10005
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
pair<int,int> v[NM],dp[GM];
int n,gm;
int main()
{
f>>n>>gm;
for(int i=1;i<=n;i++)
f>>v[i].first>>v[i].second;
for(int i=1;i<=n;i++)
for(int j=gm-v[i].first;j>=0;j--)
{
dp[j+v[i].first].second=max(dp[j+v[i].first].second,dp[j].second+v[i].second);
}
g<<dp[gm].second;
g.close();
f.close();
return 0;
}
