Cod sursa(job #1776392)
Utilizator | Diana M MDiana15 | Data | 11 octombrie 2016 11:22:32 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.55 kb |
#include <fstream>
using namespace std;
int n,i,j,gg,p[5001],w[5001],d[3][10001];
void sw()
{int i;
for(i=0;i<=gg;i++)
d[1][i]=d[2][i];
}
int main()
{
ifstream f("rucsac.in");
ofstream g("rucsac.out");
f>>n>>gg;
for(i=1;i<=n;i++)
f>>w[i]>>p[i];
for(i=1;i<=n;i++)
{for(j=0;j<=gg;j++)
{
if(w[i]<=j)
{
d[2][j]=max(d[1][j],d[1][j-w[i]]+p[i]);
}
else d[2][j]=d[1][j];
}
sw();}
g<<d[2][gg];
return 0;
}