Cod sursa(job #3223194)
Utilizator | Ilie Dumitru Ilie_Mity | Data | 12 aprilie 2024 17:17:02 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.48 kb |
// Ilie Dumitru
#include<bits/stdc++.h>
const int NMAX=5005, WMAX = 10005;
int N, W;
int max[WMAX];
int main()
{
std::ifstream f("rucsac.in");
std::ofstream g("rucsac.out");
int i, j, w, p, ans = 0;
f >> N >> W;
max[0] = 1;
for(i = 0;i < N;++i)
{
f >> w >> p;
for(j = W;j >= w;--j)
if(max[j - w] && max[j - w] + p > max[j])
max[j] = p + max[j - w];
}
for(i = 0;i <= W;++i)
if(max[i] > ans)
ans = max[i];
g << ans - 1;
return 0;
}