Cod sursa(job #819538)
#include <fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
void citire();
void pd();
void afisare();
int n, w[5001], c[5001], gmax;
int cmax[5001], uz[10001][5001];
int main()
{
citire();
pd();
afisare();
return 0;
}
void citire()
{
int i;
fin>>n>>gmax;
for(i=1;i<=n;i++)
fin>>w[i]>>c[i];
}
void pd ()
{
int g, i, j, poz, x;
for(g=1;g<=gmax;g++)
{
poz=0;
for(i=1;i<=n;i++)
{
if(w[i]<=g && uz[g-w[i]][i]==0)
x=c[i]+cmax[g-w[i]];
else
x=c[i];
if(x>cmax[g])
{
poz=i;
cmax[g]=x;
}
}
if(poz)
{
for(j=1;j<=n;j++)
uz[g][j]=uz[g-w[poz]][j];
uz[g][poz]=1;
}
}
}
void afisare()
{
int g, i, mx, poz;
for(g=1;g<=gmax;g++)
if(mx<cmax[g])
{
mx=cmax[g];
poz=g;
}
fout<<mx<<'\n';
for(i=1;i<=n;i++)
if(uz[poz][i]==1)
fout<<i<<' ';
fout<<'\n';
}