BÀI TOÁN CÁI TÚI_QUY HOẠCH ĐỘNG

Dựa theo: Giải thuật và lập trình của Lê Minh Hoàng

BÀI TOÁN CÁI TÚI:

Trong siêu thị có n gói hàng ( n<= 100), gói hàng thứ i  có trọng lượng là W[i] <= 100 và trị  giá V[i] <=100. Một tên trộm đột nhập vào siêu thị, tên trộm mang theo một cái túi có thể mang được tối đa trọng lượng M (M<= 100). Hỏi tên trộm sẽ lấy đi những gói hàng nào để được tổng giá trị lớn nhất.

INPUT:File văn bản BAG.INP

+Dòng 1: Chứa 2 số n,M cách nhau ít nhất một dấu cách

+n dòng tiếp theo: dòng i chứa 2 số nguyên dương W[i], V[i] cách nhau ít nhất một dấu cách.

Output: File văn bản BAG.OUT

+Dòng 1: Ghi giá trị lớn nhất tên trộm có thể lấy

+Dòng 2: Ghi chỉ số những gói bị lấy

BAG.INP	BAG.OUT
5      11 3      3 4      4 5      4 9      10 4      4	11 5   2   1

Cách giải:

Nếu gọi F[i,j] là giá trị lớn nhất có thể có bằng cách chọn trong các gói { 1,2,….,i } với giới hạn trọng lượng j. Thì giá trị lớn nhất khi chọn được trong số n gói giới hạn trọng lượng M chính là F[n,M].

2.1.Công thức truy hồi tính F[i,j].

Với giới hạn trọng lượng j, việc chọn tối ưu trong các gói  {1 ,2, ….., i -1, i } để có giá trị lớn nhất sẽ có 2 khả năng:

+ Nếu không chọn gói thứ i thì F[i,j] là giá trị lớn nhất có thể có bằng cách chọn trong số  các gói { 1,2,…, i -1 }  với giới hạn trọng lượng j. Tức là:

F[i,j] = F[i-1,j];

+Nếu có chọn gói thứ i ( tất nhiên chỉ xét trong trường hợp này khi mà W[i] <= j) thì F[i,j] bằng giá trị gói thứ i là V[i] cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các gói  { 1,2,…, i -1 }  với giới hạn trọng lượng j – W[i]. Tức là về mặt giá trị thu được:

F[i,j] = V[i] + F[i-1, j – W[i]];

Vì theo cách xây dựng F[i,j] là giá trị lớn nhất có thể có, nên F[i,j] sẽ là max trong 2 giá trị thu được ở trên.

2.2.Cơ sở quy hoạch động:

Dễ thấy F[0,j] = giá trị lớn nhất có thể có bằng cách chọn 0 gói = 0.

2.3.Tính bảng phương án:

Bằng phương án F gồm n+1 dòng, M+1 cột, trước tiên ta điền cơ sở quy hoạch động:

Dòng 0 gồm toàn số 0.

Sử dụng công thức truy hồi, dùng dòng 0 tính dòng 1, dùng dòng 1 tính dòng 2,….. đến khi hết dòng n.

2.4.Truy vết:

Tính xong bảng phương án thì ta quan tâm đến F[n,M] đó chính là giá trị lớn nhất thu được khi chọn trong cả n gói với giới hạn trọng lượng M.

Nếu F[n,M] = F[n-1,M] thì tức là không chọn gói thứ n, ta truy tiếp F[n-1,M]. Còn nếu F[n,M] khác

F[n-1,M] thì ta thông báo rằng phép chọn tối ưu có chọn gói thứ n và truy tiếp F[n-1,M-W[n]].Cứ tiếp tục cho tới khi lên tới bảng 0 của phương án.

// Giai thuat quy hoach dong cho bai toan cai tui

procedure Optimize; { Tim bang phuong an bang cong thuc truy hoi }

var
  i,j: Integer;
begin
  FillChar(F[0], SizeOf(F[0],0);{Dien co so quy hoach dong }
  for i:= 1 to n do
    for j:= 0 to M do
      begin { Tinh F[i,j] }
        F[i,j] := F[i-1,j]; { Gia su khong chon goi thu i thi F[i,j] = F[i-1,j] }
        {Sau do danh gia: neu chon goi thu i se duoc loi hon thi dat lai F[i,j]}
        if ( j>= W[i] and (F[i,j] < F[i-1,j-W[i]]+V[i]) then
          F[i,j] := F[i-1,j-W[i]] + V[i];
      end;
  end;
  
  procedure Trace; { Truy vet tim nghiem toi uu }
  
  var
    fo: Text;
  begin
    Assign(fo, OutputFile); Rewrite(fo);
    WriteLn(fo, F[n,M]); { In ra gia tri lon nhat co the kiem duoc }
    while n<>0 do {Truy vet tren bang phuong an tu hang n len hang 0 }
      begin
        if F[n,M] <> F[n-1,M] then {Neu co the chon goi thu n}
          begin
            Write(fo,n,' ');
            M := M - W[n];
            { Da chon goi thu n roi thi chi co the mang them M-W[n] nua thoi }
          end;
        Dec(n);
      Close(fo);
    end;
    

//Code implementation:
       //GIAI THUAT QUY HOACH DONG CHO BAI CAI TUI
#include<iostream>
#include<fstream.h>
#define MAX 100

int n,m;  
// n la so do vat va m la khoi luong toi da ma tui mang duoc
int X[MAX],Y[MAX];
 // X[i], Y[i] de luu khoi luong va gia tri cua vat thu i
int F[MAX][MAX]; 
  //F[i][j] la tong gia tri lon nhat ma tui chua duoc neu lay tu 1...i vat
  // voi khoi luong gioi han la j 

void Enter()
{
    fstream f;
    f.open("BAICAITUI.txt");
    f>>n>>m;
    for( int i =1;i<=n;++i)
      f>>X[i]>>Y[i];
    
}

void Init()
{
     for( int i =1;i<=n;++i)
       F[i][0] = 0;
}

void Optimize()
{
     for(int i =1;i<=n;++i)
     for(int j= 0;j<=m;++j)
     {
             F[i][j] = F[i-1][j]; 
          //Gia su chi chon duoc den vat thu i
             if( j >= X[i] && F[i][j] < F[i-1][j- X[i]] + Y[i])
               F[i][j] =  F[i-1][j- X[i]] + Y[i];
               
     }
}

void Trace() //Truy vet
{
     std::cout<<"Gia tri Max = " << F[n][m];
     std::cout<<std::endl;
     
     while ( n != 0)
     {
           if( F[n][m] != F[n-1][m]) // Co the chon duoc vat thu n
           {
               std::cout<< n <<std::endl;
               m -= X[n]; 
     // Da chon vat thu n thi chi con mang duoc m-Y[n] khoi luong
           }
           --n;
           
     }
}

main()
{
      Enter();
      Init();
      Optimize();
      Trace();
      system("pause");
}