Cod sursa(job #2029967)
| Utilizator | Data | 30 septembrie 2017 18:44:17 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.63 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream F("rucsac.in");
ofstream G("rucsac.out");
int n, g, w, p, d[3][10005];
int main()
{
F >> n >> g;
for(int i = 1; i <= n; ++ i)
{
F >> w >> p;
if(i%2)
{
for(int j = 1; j <= g; ++ j)
if(j < w) d[0][j]=d[1][j];
else d[0][j]=max(d[1][j], d[1][j-w]+p);
}
else
{
for(int j = 1; j <= g; ++ j)
if(j < w) d[1][j]=d[0][j];
else d[1][j]=max(d[0][j], d[0][j-w]+p);
}
}
G << d[1][g];
return 0;
}
