Cod sursa(job #2650360)
| Utilizator | Data | 18 septembrie 2020 15:05:41 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.56 kb |
#include <fstream>
using namespace std;
int d[2][10005];
int greu[5005],val[5005];
int main()
{
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int n,gr,mx=0,lin=1;
cin >> n >> gr;
for(int i=1;i<=n;i++)
cin >> greu[i] >> val[i];
for(int i=1;i<=n;i++)
{
for(int g=1;g<=gr;g++)
{
d[lin][g]=d[1-lin][g];
if(g-greu[i]>=0)
d[lin][g]=max(d[1-lin][g-greu[i]]+val[i],d[1-lin][g]);
}
lin=1-lin;
}
cout << d[1-lin][gr];
return 0;
}
