BÀI TOÁN BA LÔ 1

Tiêu đề: BÀI TOÁN BA LÔ 1 26/4/2008, 07:06

//cho n vat co khoi luong lan luot la a[0],a[1]...a[n];
//mot ba lo co kha nang chua w lan chon nhung mon nao de bo vao ba lo sao cho khoi luong chon la lon nhat
//(voi nhung n=mon chi chon mot lan
//INPUT
// n w a[i]
// 4 10 4 2 5 3
//out put
//10 2 5 3

Code:: #include <iostream>
#include <conio.h>
#include <fstream>

using namespace std;

int n,w;int k,v;
int a[100];
int b[100][100];
int chon[100];//luu vat chon
void nhap()
{
ifstream fi;
fi.open("data.txt");
cout<<"Nhap so vat va khoi luong toi da";
fi>>n>>w;
for(int i=1;i<=n;i++)
   fi>>a[i];
fi.close();

}
int MAX(int x,int y)
{
if(x>y)
   return x;
else
   return y;
}
void Taobang()
{

//chon vat thu nhat
for(v=1;v<=w;v++)
{
   if(v>=a[1])
      b[1][v]=a[1];
   else
      b[1][v]=0;
}
//chon tu vat 2 den vat n
for(k=2;k<=n;k++)
{
   for(v=1;v<=w;v++)
   {
      if(v>=a[k])
         b[k][v]=MAX(b[k-1][v-a[k]]+a[k],b[k-1][v]);
      else
         b[k][v]=b[k-1][v];
   }
}
}
void Trabang()
{
v=w;k=n;
for(int i=0;i<n;i++)
   chon[i]=0;
do{
   while((k>=2)&&(b[k][v]==b[k-1][v]))
   k--;
   chon[k]=1;
   v=b[k][v]-a[k];
}while (v!=0);
}
void xuat()
{
ofstream fo;
fo.open("out.txt");
for(int i=1;i<=n;i++)
   if(chon[i]==1)
   fo<<a[i]<<" ";
fo.close();
}
void main()
{
nhap();
Taobang();
Trabang();
xuat();
}