Pagini recente » Cod sursa (job #2367537) | Cod sursa (job #1162166) | Cod sursa (job #2754541) | Cod sursa (job #1645986) | Cod sursa (job #1089721)
#include <fstream>
using namespace std;
int w[5005], p[5005], v0[10005],v1[10005];
int n,gmax,i,j,Max;
int main() {
ifstream f("rucsac.in");
ofstream g("rucsac.out");
f>>n>>gmax;
for(i=1;i<=n;i++)
f>>w[i]>>p[i];
v0[w[1]]=p[1];
for(i=2;i<=n;i++) {
for(j=0;j<=gmax;j++)
if(w[i]<=j)
v1[j] = max(v0[j],v0[j-w[i]]+p[i]);\
else
v1[j]=v0[j];
for(j=0;j<=gmax;j++)
v0[j]=v1[j];
}
for(i=0;i<=gmax;i++)
if(v1[i]>Max)
Max=v1[i];
g<<Max<<"\n";
return 0;
}