Pagini recente » Subsecvența de sumă maximă | Monitorul de evaluare | Subsecvența de sumă maximă | Algoritmiada 2012, Runda Finală, Clasele 5-9 | Cod sursa (job #2881765)
#include<fstream>
#include<iostream>
using namespace std;
int n,ma, Gmax, g[1001], v[1001], d[1001][10001];
int main()
{
freopen("rucsac1.in","r",stdin);
freopen("rucsac1.out","w",stdout);
cin>>n;
cin>>Gmax;
for(int i=1;i<=n;i++)
{
cin>>g[i]>>v[i];
}
for(int i=0;i<=n;i++)
{
for(int j=0;j<=Gmax;j++)
{
if(j+g[i+1]<=Gmax)
d[i+1][j+g[i+1]]=max(d[i+1][j+g[i+1]], d[i][j]+v[i+1]);
d[i+1][j]=max(d[i+1][j], d[i][j]);
}
}
for(int j=1;j<=Gmax;j++)
{
ma=max(ma, d[n][j]);
}
cout<<ma;
}