Cod sursa(job #1989126)
Utilizator | Ninicu Cristian DoubleNy | Data | 5 iunie 2017 22:04:44 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 35 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.55 kb |
#include <bits/stdc++.h>
using namespace std;
int ans[5001][10001];
int wi[5001];
int pi[10001];
int main(){
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int n, s;
cin >> n >> s;
for(int i=0; i<n; i++)
cin >> wi[i] >> pi[i];
for(int i=0;i<=n;i++)
for(int w=0;w<=s; w++){
if(i == 0 || w == 0)
ans[i][w] = 0;
else if( wi[i - 1] <= w )
ans[i][w] = max( pi[i - 1] + ans[i-1][w - wi[i - 1]], ans[i - 1][w]);
else
ans[i][w] = ans[i - 1][w];
}
cout << ans[n][s] << endl;
return(0);
}