Pagini recente » Rezultatele filtrării | Rezultatele filtrării | Istoria paginii utilizator/c912014 | Rezultatele filtrării | Cod sursa (job #3228426)
#include <fstream>
using namespace std;
ofstream cout ("rucsac.out");
ifstream cin ("rucsac.in");
int w[5001],val[5001];
int dp[2][10001];
int main()
{
int n,g;
cin>>n>>g;
for(int i=1;i<=n;++i)
cin>>w[i]>>val[i];
int l=0;
for(int i = 1; i <= n; ++i, l = 1 - l)
for(int cw = 0; cw <= g; ++cw)
{
dp[1-l][cw] = dp[l][cw];
if(w[i] <= cw)
dp[1-l][cw] = max(dp[1-l][cw], dp[l][cw - w[i]] + val[i]);
}
cout<<dp[l][g];
return 0;
}