Pagini recente » Cod sursa (job #2326056) | Cod sursa (job #2555812) | Cod sursa (job #1981396) | Cod sursa (job #1057965) | Cod sursa (job #1310385)
#include<fstream>
#define NMax 5000
#define MaxG 10000
using namespace std;
int n, GMax;
int c[NMax],g[NMax];
int CMax[MaxG],Uz[MaxG][NMax];
void Citire();
void Rezolvare();
void Afisare();
int main()
{
Citire();
Rezolvare();
Afisare();
}
void Citire()
{
ifstream fin("rucsac.in");
int i,j;
fin>>n>>GMax;
for (i=1; i<=n; i++) fin>>g[i];
for (j=1; j<=n; j++) fin>>c[j];
fin.close();
}
void Rezolvare()
{
int S,k,i;
for (S=1; S<=GMax; S++) CMax[S]=-1;
for (S=1; S<=GMax; S++)
for (i=1; i<=n; i++)
if ((g[i]<=S) && (CMax[S-g[i]])!=-1 && (!Uz[S-g[i]][i]))
if(CMax[S]<c[i]+CMax[S-g[i]])
{
CMax[S]=c[i]+CMax[S-g[i]];
for(k=1; k<=n; k++)
Uz[S][k]=Uz[S-g[i]][k];
Uz[S][i]=1;
}
}
void Afisare()
{
ofstream fout("rucsac.out");
if (CMax[GMax]==-1)
fout<<"Imposibil";
else
{
fout<<CMax[GMax]<<endl;
for(int k=1; k<=n; k++)
if (Uz[GMax][k])
fout<<k<<" ";
}
fout.close();
}