Ba Bai Toan Ve Ba Lo

//Ba Lo 1
#include <iostream>
#include <iomanip>
using namespace std;

int max(int a,int b);
void taobang();
void trabang();
void xuatbang();

int f[100][100];
int chon[100],a[100],w,n;
void main()
{
   cout<<"nhap n: ";
   cin>>n;
   for(int i=1;i<=n;++i)
   {
      cout<<"a["<<i<<"]=";
      cin>>a[i];
   }
   cout<<endl<<"nhap kl max: ";
   cin>>w;

   taobang();
   cout<<"Lap Bang:"<<endl;
   xuatbang();
   cout<<"cac vat dc chon la: ";
   trabang();
   int getch();
}
void taobang()
{
   int k,v;
   for(v=1;v<=w;++v)
   {
      if(v>=a[1])
         f[1][v]=a[1];
      else      
         f[1][v]=0;
      for(k=2;k<=n;++k)
         if(v>=a[k])
            f[k][v]=max(f[k-1][v-a[k]]+a[k],f[k-1][v]);
         else
            f[k][v]=f[k-1][v];
   }
}
void trabang()
{
   int k=n,v=w;
   for(int i=1;i<=n;++i)
      chon[i]=false;
   do
   {
      while(f[k][v]==f[k-1][v]) k--;
      chon[k]=true;
      v=f[k][v]-a[k];
   }while(v>0);
   cout<<"Cac vat duocchon la: "<<endl;
   for(k=1;k<=n;++k)
      if(chon[k])
         cout<<a[k]<<' ';
}
int max(int a,int b)
{
   if(a>b) return a;
   else return b;
}
void xuatbang()
{
   cout<<"  a";
   for(int j=1;j<=w;++j)
      cout<<setw(3)<<j;
   cout<<endl;
   for(int i=1;i<=n;i++)
   {
      cout<<setw(3)<<a[i];
      for(int j=1;j<=w;++j)
         cout<<setw(3)<<f[i][j];
      cout<<endl;
   }
}

//Ba Lo 2
#include <iostream>
#include <iomanip>
using namespace std;

int max(int a,int b);
void taobang();
void trabang();
void xuatbang();

int f[100][100];
int chon[100],a[100],c[100],w,n;
void main()
{
   cout<<"nhap n: ";
   cin>>n;
   for(int i=1;i<=n;++i)
   {
      cout<<"vat thu "<<i<<endl;
      cout<<"a["<<i<<"]=";cin>>a[i];
      cout<<"c["<<i<<"]=";cin>>c[i];
   }
   cout<<endl<<"nhap kl max ma bolo chiu duoc: ";
   cin>>w;

   taobang();
   cout<<"Lap Bang:"<<endl;
   xuatbang();
   cout<<"nhung vat can tim la: \n";
   trabang();
}
void taobang()
{
   int k,v;
   for(v=1;v<=w;++v)
   {
      if(v>=a[1])
         f[1][v]=c[1];
      else      
         f[1][v]=0;
      for(k=2;k<=n;++k)
         if(v>=a[k])
            f[k][v]=max(f[k-1][v-a[k]]+c[k],f[k-1][v]);
         else
            f[k][v]=f[k-1][v];
   }
}
void trabang()
{
   int k=n,v=w;
   for(int i=1;i<=n;++i)
      chon[i]=false;
   do
   {
      while(f[k][v]==f[k-1][v]) k--;
      while(f[k][v]==f[k][v-1]) v--;
      chon[k]=true;
      v=v-a[k];
      if(k>1)--k;
   }while(v>0);
   cout<<"  a  c"<<endl;
   for(k=1;k<=n;++k)
      if(chon[k])
         cout<<setw(3)<<a[k]<<setw(3)<<c[k]<<endl;
}
int max(int a,int b)
{
   if(a>b) return a;
   else return b;
}
void xuatbang()
{
   cout<<"  a  c";
   for(int j=1;j<=w;++j)
      cout<<setw(3)<<j;
   cout<<endl;
   for(int i=1;i<=n;i++)
   {
      cout<<setw(3)<<a[i]<<setw(3)<<c[i];
      for(int j=1;j<=w;++j)
         cout<<setw(3)<<f[i][j];
      cout<<endl;
   }
}

//Ba Lo 3
#include <iostream>
#include <iomanip>
using namespace std;

int max(int a,int b);
void taobang();
void trabang();
void xuatbang();

int f[100][100];
int chon[100],a[100],a1[100],c1[100],c[100],soluong[100],w,n,dem=0;
void main()
{
   cout<<"nhap n: ";
   cin>>n;
   for(int i=1;i<=n;++i)
   {
      cout<<"vat thu "<<i<<endl;
      cout<<"a["<<i<<"]=";cin>>a[i];
      cout<<"c["<<i<<"]=";cin>>c[i];
      cout<<"So Luong: ";cin>>soluong[i];
   }
   for(i=1;i<=n;++i)
      for(int j=1;j<=soluong[i];++j)
      {
         dem++;
         a1[dem]=a[i];
         c1[dem]=c[i];
      }
   cout<<endl<<"nhap kl max ma balo chiu duoc: ";
   cin>>w;

   taobang();
   cout<<"Lap Bang:"<<endl;
   xuatbang();
   cout<<"nhung vat can tim la: \n";
   trabang();
}
void taobang()
{
   int k,v;
   for(v=1;v<=w;++v)
   {
      if(v>=a1[1])
         f[1][v]=c1[1];
      else      
         f[1][v]=0;
      for(k=2;k<=dem;++k)
         if(v>=a1[k])
            f[k][v]=max(f[k-1][v-a1[k]]+c1[k],f[k-1][v]);
         else
            f[k][v]=f[k-1][v];
   }
}
void trabang()
{
   int k=dem,v=w;
   for(int i=1;i<=dem;++i)
      chon[i]=false;
   do
   {
      while(f[k][v]==f[k-1][v]) k--;
      while(f[k][v]==f[k][v-1]) v--;
      chon[k]=true;
      v=v-a1[k];
      if(k>1)--k;
   }while(v>0);
   int a2=0,c2=0,t=0,t1=0;a1[dem+1]=0;c1[dem+1]=0;chon[dem+1]=true;
   cout<<"  a  c"<<endl;
   for(k=1;k<=dem+1;++k)
      if(chon[k])
      {
         ++t1;
         if(a2==a1[k] && c2==c1[k])
            t++;
         else
         {
            if(t1>0)
               cout<<setw(3)<<a2<<setw(3)<<c2<<" So Luong: "<<t<<endl;
            a2=a1[k];c2=c1[k];t=1;
         }
      }
}
int max(int a,int b)
{
   if(a>b) return a;
   else return b;
}
void xuatbang()
{
   cout<<"  a  c";
   for(int j=1;j<=w;++j)
      cout<<setw(3)<<j;
   cout<<endl;
   for(int i=1;i<=dem;i++)
   {
      cout<<setw(3)<<a1[i]<<setw(3)<<c1[i];
      for(int j=1;j<=w;++j)
         cout<<setw(3)<<f[i][j];
      cout<<endl;
   }
}