A GIẢI THUẬT THAM ĂN

1. Bài toán

Cho một cái ba lô có thể đựng một trọng lượng W và n loại đồ vật, mỗi đồ vật i có một trọng lượng gi và một giá trị vi. Tất cả các loại đồ vật đều có số lượng không hạn chế. Tìm một cách lựa chọn các đồ vật đựng vào ba lô, chọn các loại đồ vật nào, mỗi loại lấy bao nhiêu sao cho tổng trọng lượng không vượt quá W và tổng giá trị là lớn nhất.

Theo yêu cầu của bài toán thì ta cần những đồ vật có giá trị cao mà trọng lượng lại nhỏ để sao cho có thể mang được nhiều “đồ quý”, sẽ là hợp lý khi ta quan tâm đến yếu tố “đơn giá” của từng loại đồ vật tức là tỷ lệ giá trị/trọng lượng. Ðơn giá càng cao thì đồ càng quý. Từ đó ta có kỹ thuậtgreedy áp dụng cho bài toán này là:

  • 1.       Tính đơn giá cho các loại đồ vật.
  • 2.       Xét các loại đồ vật theo thứ tự đơn giá từ lớn đến nhỏ.
  • 3.       Với mỗi đồ vật được xét sẽ lấy một số lượng tối đa mà trọng lượng còn lại của ba lô cho phép.
  • 4.       Xác định trọng luợng còn lại của ba lô và quay lại bước 3 cho đến khi không còn có thể chọn được đồ vật nào nữa.

2. Ví dụ

Ta có một ba lô có trọng lượng là 37 và 4 loại đồ vật với trọng lượng và giá trị tương ứng được cho trong bảng bên dưới:

Loại đồ vật Trọng lượng Giá trị
A 15 30
B 10 25
C 2 2
D 4 6

Từ bảng đã cho ta tính đơn giá cho các loại đồ vật và sắp xếp các loại đồ vật này theo thứ tự đơn giá giảm dần ta có bảng sau.

Loại đồ vật

Trọng lượng

Giá trị

Đơn giá

B

10

25

2.5

A

15

30

2.0

D

4

6

1.5

C

2

2

1.0

Theo đó thì thứ tự ưu tiên để chọn đồ vật là là B, A, D và cuối cùng là C.

Vật B được xét đầu tiên và ta chọn tối đa 3 cái vì mỗi cái vì trọng lượng mỗi cái là 10 và ba lô có trọng lượng 37. Sau khi đã chọn 3 vât loại B, trọng lượng còn lại trong ba lô là 37 – 3*10 = 7. Ta xét đến vật A, vì A có trọng lượng 15 mà trọng lượng còn lại của balô chỉ còn 7 nên không thể chọn vật A. Xét vật D và ta thấy có thể chọn 1 vật D, khi đó trọng lượng còn lại của ba lô là 7-4 = 3. Cuối cùng ta chọn được một vật C.

Như vậy chúng ta đã chọn 3 cái loại B, một cái loại D và 1 cái loại C. Tổng trọng lương là 3*10 + 1*4 + 1*2 = 36 và tổng giá trị là 3*25+1*6+1*2 = 83.

3. Giải thuật tham ăn

Giải thuật thô giải bài toán cái ba lô bằng kỹ thuật tham ăn như sau:

Tổ chức dữ liệu:

  • Mỗi đồ vật được biểu diễn bởi một mẩu tin có các trường:
    • o        Ten: Lưu trữ tên đồ vật.
    • o        Trong_luong: Lưu trữ trọng lượng của đồ vật.
    • o        Gia_tri: Lưu trữ giá trị của đồ vật
    • o        Don_gia: Lưu trữ đơn giá của đồ vật
    • o        Phuong_an: Lưu trữ số lượng đồ vật được chọn theo phương án.
  • Danh sách các đồ vật được biểu diễn bởi một mảng các đồ vật.

#define MAX_SIZE   100

typedef struct {

            char Ten [20];

            float Trong_luong, Gia_tri, Don_gia;

            int Phuong_an;

} Do_vat;

typdef Do_vat Danh_sach_do_vat[MAX_SIZE];

void Greedy (Danh_sach_do_vat dsdv, float W) {

            int i;

            /*Sắp xếp mảng dsdv theo thứ tự giảm của don_gia*/

            for (i = 0; i < n; i++) {

                        dsdv[i].Phuong_an = Chon(dsdv[i].Trong_luong, W);

                        W = W – dsdv[i].phuong_an * dsdv[i].Trong_luong;

            }

}

Trong đó hàm Chon(trong_luong, W) nhận vào trọng lượng trong_luong của một vật và trọng lượng còn lại W của ba lô, trả về số lượng đồ vật được chọn, sao cho tổng trọng lượng của các vật được chọn không lớn hơn W. Nói riêng, trong trường hợp trong_luong và W là hai sô nguyên thì Chon(Trong_luong, W) chính là W DIV Trong_luong.

4. Biến thể của bài toán cái ba lô

Chú ý: Có một số biến thể của bài toán cái ba lô như sau:

  1. Mỗi đồ vật i chỉ có một số lượng si. Với bài toán này khi lựa chọn vật i ta không được lấy một số lượng vượt quá si.
  2. Mỗi đồ vật chỉ có một cái. Với bài toán này thì với mỗi đồ vật ta chỉ có thể chọn hoặc không chọn.
B. GIẢI THUẬT NHÁNH CẬN
1. Phát biểu

Ta thấy đây là một bài toán tìm max. Danh sách các đồ vật được sắp xếp theo thứ tự giảm của đơn giá để xét phân nhánh.

1.       Nút gốc biểu diễn cho trạng thái ban đầu của ba lô, ở đó ta chưa chọn một vật nào. Tổng giá trị được chọn TGT = 0. Cận trên của nút gốc CT = W * Ðơn giá lớn nhất.

2.       Nút gốc sẽ có các nút con tương ứng với các khả năng chọn đồ vật có đơn giá lớn nhất. Với mỗi nút con ta tính lại các thông số:

  • TGT = TGT (của nút cha) + số đồ vật được chọn * giá trị mỗi vật.
  • W  = W (của nút cha) – số đồ vật được chọn * trọng lượng mỗi vật.
  • CT = TGT + W * Ðơn giá của vật sẽ xét kế tiếp.

3.       Trong các nút con, ta sẽ ưu tiên phân nhánh cho nút con nào có cận trên lớn hơn trước. Các con của nút này tương ứng với các khả năng chọn đồ vật có đơn giá lớn tiếp theo. Với mỗi nút ta lại phải xác định lại các thông số TGT, W, CT theo công thức đã nói trong bước 2.

4.       Lặp lại bước 3 với chú ý: đối với những nút có cận trên nhỏ hơn hoặc bằng giá lớn nhất tạm thời của một phương án đã được tìm thấy thì ta không cần phân nhánh cho nút đó nữa (cắt bỏ).

5.       Nếu tất cả các nút đều đã được phân nhánh hoặc bị cắt bỏ thì phương án có giá lớn nhất là phương án cần tìm.

2. Kỹ thuật

Với bài toán cái ba lô đã cho trong ví dụ trước, sau khi tính đơn giá cho các đồ vật và sắp xếp các đồ vật theo thứ tự giảm dần của đơn giá ta được bảng sau:

Loại đồ vật

Trọng lượng

Giá trị

Đơn giá

b

10

25

2.5

a

15

30

2.0

d

4

6

1.5

c

2

2

1

Gọi  XA, XB, XC, Xlà số lượng cần chọn tương ứng của các đồ vật a, b, c d.

Nút gốc A biểu diễn cho trạng thái ta chưa chọn bất cứ một đồ vật nào. Khi đó tổng giá trị TGT =0, trọng lượng của ba lô W=37 (theo đề ra) và cận trên CT = 37*2.5 = 92.5, trong đó 37 là W, 2.5 là đơn giá của đồ vật b.

Với đồ vật b, ta có 4 khả năng: chọn 3 đồ vật b (XB=3), chọn 2 đồ vật b (XB=2), chọn 1 đồ vật b (XB=1) và không chọn đồ vật b (XB=0). Ứng với 4 khả năng này, ta phân nhánh cho nút gốc A thành 4 con B, C, D và E.

Với nút con B, ta có TGT = 0+ 3*25 = 75, trong đó 3 là số vật b được chọn, 25 là giá trị của mỗi đồ vật b. W = 37- 3*10 = 7, trong đó 37 là trọnh lượng ban đầu của ba lô, 3 là số vật b được, 10 là trọng lượng mõi đồ vật b. CT = 75 + 7*2 = 89, trong đó 75 là TGT, 7 là trọng lượng còn lại của ba lô và 2 là đơn giá của đồ vật a. Tương tự ta tính được các thông số cho các nút C, D và E, trong đó cận trên tương ứng là 84, 79 và 74.

Trong các nút B, C, D và E thì nút B có cận trên lớn nhất nên ta sẽ phân nhánh cho nút B trước với hy vọng sẽ có được phương án tốt từ hướng này. Từ nút B ta chỉ có một nút con F duy nhất ứng với XA=0 (do trọng lượng còn lại của ba lô là 7, trong khi trọng lượng của mỗi đồ vật a là 15). Sau khi xác định các thông số cho nút F ta có cận trên của F là 85.5. Ta tiếp tục phân nhánh cho nút F. Nút F có 2 con G và H tương ứng với XD=1 và XD=0. Sau khi xác định các thông số cho hai nút này ta thấy cận trên của G là 84 và của H là 82 nên ta tiếp tục phân nhánh cho nút G. Nút G có hai con là I và J tương ứng với XC=1 và XC=0. Ðây là hai nút lá (biểu diễn cho phương án) vì với mỗi nút thì số các đồ vật đã được chọn xong. Trong đó nút I biểu diễn cho phương án chọn XB=3, XA=0, XD=1 và XC=1 với giá 83, trong khi nút J biểu diễn cho phương án chọn XB=3, XA=0, XD=1 và XC=0 với giá 81. Như vậy giá lớn nhất tạm thời ở đây là 83.

Quay lui lên nút H, ta thấy cận trên của H là 82<83 nên cắt tỉa nút H.

Quay lui lên nút C, ta thấy cận trên của C là 84>83 nên tiếp tục phân nhánh cho nút C. Nút C có hai con là K và L ứng với XA=1 và XA=0. Sau khi tính các thông số cho K và L ta thấy cận trên của K là 83 và của L là 75.25. Cả hai giá trị này đều không lớn hơn 83 nên cả hai nút này đều bị cắt tỉa. Cuối cùng các nút D và E cũng bị cắt tỉa. Như vậy tất cả các nút trên cây đều đã được phân nhánh hoặc bị cắt tỉa nên phương án tốt nhất tạm thời là phương án cần tìm. Theo đó ta cần chọn 3 đồ vật loại b, 1 đồ vật loại d và một đồ vật loại c với tổng giá trị là 83, tổng trọng lượng là 36 (xem hình minh họa).

3. Minh họa kỹ thuật nhánh cận cho bài toán cái ba lô

C. GIẢI THUẬT QUY HOẠCH ĐỘNG

1. Bài toán cái ba lô 

Sử dụng kỹ thuật quy hoạch động để giải bài toán cái ba lô với một lưu ý là các số liệu đều cho dưới dạng số nguyên.

Giả sử X[k,V] là số lượng đồ vật k được chọn, F[k,V] là tổng giá trị của k đồ vật đã được chọn và V là trọng lượng còn lại của ba lô, k = 1..n, V = 1..W.

Trong trường hợp đơn giản nhất, khi chỉ có một đồ vật, ta tính được X[1,V] và F[1,V] với mọi V từ 1 đến W như sau:

X[1,V] = V DIV g1 và F[1,V] = X[1,V] * v1.

Giả sử ta đã tính được F[k-1,V], khi có thêm đồ vật thứ k, ta sẽ tính được F[k,V], với mọi V từ 1 đến W. Cách tính như sau: Nếu ta chọn xk đồ vật loại k, thì trọng lượng còn lại của ba lô dành cho k-1 đồ vật từ 1 đến k-1 là U = V-xk*gk và tổng giá trị của k loại đồ vật đã được chọn F[k,V] = F[k-1,U] + xk*vk, với xk thay đổi từ 0 đến yk= V DIV gk và ta sẽ chọn xk sao cho F[k,V] lớn nhất.

Ta có công thức truy hồi như sau:

X[1,V] = V DIV g1 và F[1,V] = X[1,V] * v1.

F[k,V] = Max(F[k-1,V-xk*gk] + xk*vk) với xk chạy từ 0 đến V DIV gk.

Sau khi xác định được F[k,V] thì X[k,V] là xk ứng với giá trị F[k,V] được chọn trong công thức trên.

Để lưu các giá trị trung gian trong quá trình tính F[k,V] theo công thức truy hồi trên, ta sử dụng một bảng gồm n dòng từ 1 đến n, dòng thứ k ứng với đồ vật loại k và W+1 cột từ 0 đến W, cột thứ V ứng với trọng lượng V. Mỗi cột V bao gồm hai cột nhỏ, cột bên trái lưu F[k,V], cột bên phải lưu X[k,V]. Trong lập trình ta sẽ tổ chức hai bảng tách rời là F và X.

2. Bài toán cái ba lô – ví dụ

Ví dụ bài toán cái ba lô với trọng lượng W=9, và 5 loại đồ vật được cho trong bảng sau

Đồ vật

Trọng lượng (gi)

Giá trị (vi)

1

3

4

2

4

5

3

5

6

4

2

3

5

1

1

Ta có bảng F[k,V] và X[k,V] như sau, trong đó mỗi cột V có hai cột con, cột bên trái ghi F[k,V] và cột bên phải ghi X[k,V].

    v   k

0

1

2

3

4

5

6

7

8

9

1 0 0 0 0 0 0 4 1 4 1 4 1 8 2 8 2 8 2 12 3
2 0 0 0 0 0 0 4 0 5 1 5 1 8 0 9 1 10 2 12 0
3 0 0 0 0 0 0 4 0 5 0 6 1 8 0 9 0 10 0 12 0
4 0 0 0 0 3 1 4 0 6 2 7 1 9 3 10 2 12 4 13 3
5 0 0 1 1 3 0 4 0 6 0 7 0 9 0 10 0 12 0 13 0

Trong bảng trên, việc điền giá trị cho dòng 1 rất đơn giản bằng cách sử dụng công thức: X[1,V] = V DIV g1 và F[1,V] = X[1,V] * v1.

Từ dòng 2 đến dòng 5, phải sử dụng công thức truy hồi:

F[k,V] = Max(F[k-1,V-xk*gk] + xk*vk) với xk chạy từ 0 đến V DIV gk.

Ví dụ để tính F[2,7], ta có xk chạy từ 0 đến V DIV gk, trong trường hợp này là xk chạy từ 0 đến 7 DIV 4, tức xk có hai giá trị 0 và 1.

Khi đó F[2,7] = Max (F[2-1, 7-0*4] + 0*5, F[2-1,7-1*4] + 1*5)

= Max(F[1,7], F[1,3] + 5) = Max(8, 4+5) = 9.

F[2,7] = 9 ứng với xk = 1 do đó X[2,7] = 1.

Vấn đề bây giờ là cần phải tra trong bảng trên để xác định phương án.

Khởi đầu, trọng lượng còn lại của ba lô V = W.

Xét các đồ vật từ n đến 1, với mỗi đồ vật k, ứng với trọng lượng còn lại V của ba lô, nếu X[k,V] > 0 thì chọn X[k,V] đồ vật loại k. Tính lại V = V –  X[k,V] * gk.

Ví dụ, trong bảng trên, ta sẽ xét các đồ vật từ 5 đến 1. Khởi đầu V = W = 9.

Với k = 5, vì X[5,9] = 0 nên ta không chọn đồ vật loại 5.

Với k = 4, vì X[4,9] = 3 nên ta chọn 3 đồ vật loại 4. Tính lại V = 9 – 3 * 2 = 3.

Với k = 3, vì X[3,3] = 0 nên ta không chọn đồ vật loại 3.

Với k = 2, vì X[2,3] = 0 nên ta không chọn đồ vật loại 2.

Với k = 1, vì X[1,3] = 1 nên ta chọn 1 đồ vật loại 1. Tính lại V = 3 – 1 * 3 = 0.

Vậy tổng trọng lương các vật được chọn là 3 * 2 + 1 * 3 = 9. Tổng giá trị các vật được chọn là 3 * 3 + 1 * 4 = 13.

3. Giải thuật quy hoạch động cho bài toán cái ba lô

Giải thuật thô theo kỹ thuật quy hoạch động như sau:

Tổ chức dữ liệu:

  • §         Mỗi đồ vật được biểu diễn bởi một mẩu tin có các trường:
    • o        Ten: Lưu trữ tên đồ vật.
    • o        Trong_luong: Lưu trữ trọng lượng của đồ vật.
    • o        Gia_tri: Lưu trữ giá trị của đồ vật
    • o        Phuong_an: Lưu trữ số lượng đồ vật được chọn theo phương án.
  • §         Danh sách các đồ vật được biểu diễn bởi một mảng các đồ vật.
  • §         Bảng được biểu diễn bởi một mảng hai chiều các số nguyên để lưu trữ các giá trị F[k,v] và X[k,v].

Khai báo bằng C/C++:

#define MAX 100

typedef struct {

            char Ten[20];

            int Trong_luong, Gia_tri;

            int Phuong_an;

} Do_vat;

typedef Do_vat Danh_sach_vat[MAX];

typedef int Bang[10][100];

Thủ tục tạo bảng

Thủ tục tạo bảng nhận vào ds_vat là danh sách các vật, n là số lượng các loại vật, W là trọng lượng của ba lô. F và X là hai tham số thuộc kiểu Bang và được truyền bằng tham chiếu để nhận lại hai bảng F và X do thủ tục tạo ra.

void PROCEDURE Tao_Bang (Danh_sach_vat ds_vat, int n, int W, Bang F, Bang X) {

            int xk, yk, k;

            int FMax, XMax, v;

            /*Lấp đầy hàng đầu tiên của hai bảng*/

            for (v= 0; v <= W; v++) {

                        X[1, v] = v / ds_vat[1].trong_luong;

                        F[1, v] = X[1, v] * ds_vat[1].gia_tri;

            }

            /*Lấp đầy các hàng còn lại*/

            for (k = 2; k <= n; k++) {

                        X[k, 0] = 0;

                        F[1, 0] = 0;

                        for ( v= 1; v <= W; v++) {

                                    FMax := F[k-1, v] ;

                                    XMax := 0;

                                    yk := v / ds_vat[k].trong_luong;

                                    for (xk= 1; xk <= yk; xk++)

                                                if (F[k-1,v-xk*ds_vat[k].trong_luong]+xk*ds_vat[k].gia_tri>FMax) {

                                                            FMax:=F[k-1,v-k*ds_vat[k].trong_luong]+xk*ds_vat[k].gia_tri;

                                                            XMax:= xk;

                                                }

                                    F[k, v] := FMax;

                                    X[k, v] := XMax;

                        }

            }

}

Thủ tục tra bảng

Thủ tục Tra_bang nhận vào hai bảng F và X; n là số lượng các loại đồ vật, W là trọng lượng của ba lô và trả ra ds_vat là một danh sách đồ vật đã được xác định phương án.

void Tra_Bang(Danh_sach_vat ds_vat, int n, int W Bang F, Bang X) {

            int k, v;

            v = W;

            for (k = n; k >=1; k–)

                        if (X[k,v] > 0) {

                                    ds_vat[k].Phuong_an := X[k,v];

                                    v := v – X[k, v] * ds_vat[k].trong_luong;

                        }

}