Cod sursa(job #2771414)
Utilizator | Carina Maria Viespescu carinamaria | Data | 27 august 2021 11:16:44 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 50 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.6 kb |
#include <fstream>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int v[1001], p[1001];
int f[50001];
int n, sol, i, j, G, sMaxim;
int main () {
cin>>n>>G;
for (i=1;i<=n;i++){
cin>>v[i]>>p[i];
}
for (i=1;i<=n;i++){
for (j=G;j>=1;j--){
if (f[j]!=0){
if (j+v[i]<=G && f[j]+p[i]>f[j+v[i]])
f[j+v[i]]=f[j]+p[i];
}
}
if (v[i]<=G && p[i]>f[v[i]])
f[v[i]]=p[i];
}
for (i=1;i<=G;i++){
sol=max(sol, f[i]);
}
cout<<sol;
}