Cod sursa(job #1310377)

Utilizator kasperDorin Puscasu kasper Data 6 ianuarie 2015 19:20:28
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<fstream>
#define NMax 101
#define MaxG 301

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();

 }