Pagini recente » Cod sursa (job #13248) | Cod sursa (job #3223078)
#include <fstream>
#include<cmath>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int dp[5001][10001], mat[5001][10001];
int N,G,Pmax;
struct idk{
int g,profit;
};
idk ob[10001];
int main()
{
int i,j,maxim;
f>>N>>G;
for(i=1;i<=N;i++)
{
f>>ob[i].g;
f>>ob[i].profit;
}
/*for(i=1;i<=N;i++)
{
f>>mat[i][1];
f>>mat[i][2];
} */
dp[1][ob[1].g]=ob[1].profit;
dp[1][0]=0;
for(i=1;i<=N;i++)
{
int lin_c=i%2;
int lin_ant=1-i%2;
for(j=1;j<=G;j++)
{
if(j-ob[i].g<0)
maxim=dp[lin_ant][j];
else
maxim=max(dp[lin_ant][j-ob[i].g] + ob[i].profit , dp[lin_ant][j]);
//dp[lin_c][j]=max(dp[lin_ant][j-ob[i].g] + ob[i].profit , dp[lin_ant][[j]); //??
dp[lin_c][j]=maxim;
}
}
for(j=1;j<=G;j++)
Pmax=max(Pmax,dp[N%2][j]);
g<<Pmax;
f.close();
g.close();
return 0;
}