Details

Written by: Numele Real

Category: Uncategorised

Published: 06 October 2024

#include<iostream>
#include<fstream>
using namespace std;
struct obiect {int g,c;};
obiect a[20];
int n,G,p[20][20],C[20][20];
fstream f("pd4.txt",ios::in);
void init()
{ int i,j;
  for(i=0;i<=4;i++)
   for(j=0;j<=10;j++)
     { C[i][j]=0; p[i][j]=0; }
}

void citeste()
{ int i; f>>n>>G;
  for(i=1;i<=n;i++) f>>a[i].g>>a[i].c;
  f.close();
    cout<<n<<' '<<G<<' '<<endl;
    for(i=1;i<=n;i++)
    cout<<a[i].g<<' '<<a[i].c<<endl;
}
void p_dinamica()
{  int i,j;
  C[1][1]=0; p[1][1]=0;
  for(j=2;j<=10;j++) C[1][j]=a[1].c;
  for(j=2;j<=10;j++) p[1][j]=1;

  for(i=2;i<=n;i++)
   { for(j=1;j<=G;j++)
     { if((a[i].g<=j) && (a[i].c+C[i-1][j-a[i].g]>C[i-1][j]) && i>1)
          {C[i][j]=a[i].c+C[i-1][j-a[i].g]; p[i][j]=i;}
       else {C[i][j]=C[i-1][j]; p[i][j]=p[i-1][j];}
     }
   }
}

void afiseaza()
{ int i=n,j=G,k;
  cout<<"profit total "<<C[n][G]<<endl;
  while(p[i][j]!=0)
  { k=p[i][j];
    cout<<"Obiectul "<<k<<" Cu greutatea "<<a[k].g;
    cout<<" si profitul "<<a[k].c<<endl;
    j-=a[p[i][j]].g;
    while(p[i][j]==k) i--;
  }
for(i=1;i<=4;i++)
{ for(j=1;j<=10;j++) cout<<C[i][j]<<' ';
  cout<<endl;
}
}

int main()
{citeste();
 p_dinamica();
 afiseaza();
 return 0;
}