Bài kiểm tra kỳ 3 môn CTDL>

ĐỀ SỐ 1

Viết chương trình tìm X = (x₁, x₂,..,x_n)và giá trị f(X) của hàm  đạt giá trị lớn nhất. Trong đó, , c_i, a_i, b là các số nguyên dương, n £ 100. 

Dữ liệu vào n, c_j, a_j, b  được cho trong file data.in theo khuôn dạng sau:

·       Dòng đầu tiên ghi lại số tự nhiên n và b. Hai số được ghi cách nhau bởi một vài ký tự trống;

·       Dòng kế tiếp ghi lại n số c_i (i=1, 2, .., n). Hai số được ghi cách nhau bởi một vài ký tự trống;

·       Dòng cuối cùng ghi lại n số a_i (i = 1, 2, ..,n). Hai số được ghi cách nhau bởi một vài ký tự trống.

Giá trị tối ưu f(x₁,x₂,..,x_n)và phương án tối ưu X = (x₁, x₂,..,x_n)tìm được ghi lại trong file ketqua.outtheo khuôn dạng sau:

·       Dòng đầu tiên ghi lại giá trị tối ưu  f(x₁,x₂,..,x_n);

·       Dòng kế tiếp ghi lại phương án tối ưu X = (x₁, x₂,..,x_n). Hai phần tử khác nhau của X được ghi cách nhau bởi một vài khoảng trống.

Ví dụ dưới đây sẽ minh họa cho file data.in và ketqua.out của bài toán:

Data.in	Ketqua.out
4  10 5        1        9        3 5        3        6        4	12 0        0        1        1

//DeSo1.cpp
/*:
 Programmer: Nguyen Thi Khuyen Thu _ D10CN5
 Date:5/5/2012
 Description: Kiem tra cuoi ky
*/
/*:
 Viet chuong trinh tim X = (x[1],x[2],...,x[n]) va gia tri cua ham f(X) = Tong(c[i],x[i]) voi i=1->n
 sao cho f(X) dat MAX
 Trong do:
  X=(x[1],x[2],...,x[n]) = Tong(a[i]*x[i])<=b voi x[i] = {0,1}
  c[i],a[i],b la cac so nguyen duong va n<=100

 Input:
  Nhap tu file DeSo1.txt thong tin: n,c[j],a[j],b
  +Dong 1: Ghi lai 2 so tu nhien n va b
  +Dong 2: Ghi lai n so c[i]
  +Dong 3: Ghi lai n so a[i]
 Output:
  +In ra file GiaiDeSo1.txt
  +Dong 1: Gia tri toi uu cua f(x)
  +Dong 2: Phuong an toi uu X=(x[1],x[2],...,x[n])
*/
/*:
 Giai thuat:
  Neu goi L[i][j] la gia tri lon nhat cua f(x1,...,x[i]) sao cho X<=j
 Nhu vay: L[n][b] la dap so cua bai toan (gia tri MAX) co duoc neu chon n phan tu va co X khong vuot qua b
 Ta co:
  L[i][0] = L[0][j] = 0;
  L[i][j] = L[i-1][j] neu j<a[i]
  L[i][j] = max(L[i-1][j], L[i-1][j-x[i]]+c[i]) neu j>=a[i]
  trong so:
   L[i-1][j] neu khong chon vat i
   L[i-1][j-x[i]]+x[i] neu chon vat i
*/
#include<iostream>
#include<fstream>
#include<stdlib.h>
#define MAX 100
using namespace std;
ifstream infile("DeSo1.txt");
ofstream outfile("GiaiDeSo1.txt");

void Nhap(int &n, int &b, int c[], int a[])
{
 int i;
 infile>>n>>b;
 for(i=1;i<=n;++i)infile>>c[i];
 for(i=1;i<=n;++i)infile>>a[i];
}

int Max(int x, int y)
{
 return(x>y?x:y);
}


void tim(int n, int b, int c[], int a[])
{
 int L[n+1][b+1],i,j, x[n+1],max;
 for(i=0;i<=n;++i)
 {
  L[i][0] = 0;
  x[i] = 0;
 }
 for(i=0;i<=b;++i)L[0][i] = 0;

 for(i=1;i<=n;++i)
  for(j=1;j<=b;++j)
  {
   if(j<a[i])L[i][j] = L[i-1][j]; //Khong lay vat i
   else L[i][j] = Max(L[i-1][j],L[i-1][j-a[i]]+c[i]);
  }
   max = L[n][b];
  outfile<<max<<endl;
  i = n;
 while(max>0)
 {
  for(j=1;j<=i;++j)
  {
   if(L[j][b] == max)
   {
    x[j] = 1;
    i = j;
    max -= c[i];
    b -= a[i];
   }
  }
    }
    for(i=1;i<=n;++i)outfile<<x[i]<<" ";
 
}

int main()
{
 int n,b,c[MAX],a[MAX];
 if(!infile.is_open())
 {
  outfile<<endl<<"Can't open  the file.";
  return  0;
 }
 Nhap(n,b,c,a);
 tim(n,b,c,a);
 return 0;
 
}

*