Cod sursa(job #1310334)

Utilizator kasperDorin Puscasu kasper Data 6 ianuarie 2015 18:44:04
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("rucsacul.in");
     int i,j;
     fin>>n>>GMax;
     for (i=1; i<=n; i++) fin>>g[i];
     for (i=1; i<=n; i++) fin>>c[i];
     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();

 }