SỬ DỤNG PHƯƠNG PHÁP QUY HOẠCH ĐỘNG
GIẢI BÀI TOÁN BA LÔ 0-1
Bài toán xếp ba lô (Knapsack problem) là một bài toán tối ưu hóa tổ hợp
(combinatorial optimization). Cho một tập hợp các phần tử, mỗi phần tử có
trọng lượng và giá trị khác nhau, xác định các phần tử có thể đưa vào một tập
hợp khác sao cho trọng lượng bé hơn hoặc bằng một giới hạn cho trước, và tổng
giá trị các phần tử là lớn nhất. Tên của bài toán bắt nguồn từ việc phải xếp các
đồ vật ba lô sao cho chứa được nhiều đồ có giá trị nhất.

Một cách phát biểu khác về bài toán:
Một tên trộm sau khi đột nhập vào nhà thì thấy có N loại đồ vật có kích
thước và giá trị khác nhau. Vật gì hắn ta cũng muốn mang đi, nhưng lại chỉ
mang một chiếc túi có dung lượng M (có thể chứa được một số đồ vật sao cho
tổng kích thước chỉ nhỏ hơn hay bằng M). Vấn đề đặt ra cho tên trộm là hắn
phải chọn lựa một danh sách các đồ vật sẽ mang đi sao cho tổng giá trị lấy cắp là
lớn nhất.
Sơ lược về Quy hoạch động (Dynamic programming)
Ý tưởng để phát triển một thuật toán quy hoạch động cho bài toán xếp
ba lô:
Bước 1: Cấu trúc: Tìm ra đặc điểm cấu trúc của phương án tối ưu.
Phân rã vấn đề lớn thành nhiều vấn đề nhỏ hơn. Tìm ra sự liên kết giữa cấu trúc
của phương án tối ưu và giải pháp của từng vấn đề nhỏ.

1


Bước 2: Nguyên tắc tối ưu: Định nghĩa giá trị của một phương án tối ưu
bằng phương pháp đệ quy. Thể hiện giải pháp của vấn đề gốc bằng các giải pháp
cho từng vấn đề nhỏ hơn.
Bước 3: Tính từ dưới lên (bottom-up computation): Tính toán giá trị của
một giải pháp tối ưu bằng cách tính toán từ dưới lên bằng cách sử dụng cấu trúc

3. Tính từ-dưới-lên (bottom-up computing)
Đáy: V[0, w] = 0 với tất cả 0 ≤ w ≤ W
Các dòng khác được tính từng dòng một:
V[i,w] = Max(V[i−1,w], vi+V[i−1,w−wi])
V[i,w]
0
1
2
...
...
n

0
0

1
0

2
0

3
0

...
0

...
0


V[i,w] w=0
0
1
2
3

1

2

3

4

5

Keep
0
1
2
3

1

2

3

4



0
1
2
3

0
0

0
0

0
0

0
5

0

0

Keep
0
1
2
3

0
0

0
1
0
2
3

1
0
0

2
0
0

3
0
5

4
0
5

5
0
5

Keep
0
1
2

V[2, 4] = 5 Lý do như trên
V[2, 5] = 8 Tương tự trên, ta chọn phần tử trước nó có giá trị cao hơn phần
tử hiện hành, nhưng vẫn còn trống 2 đơn vị, do đó ta vẫn có thể bỏ vào thêm
V[2,2] = 2. Tổng cộng có V[2, 5] = V[1, 5] + V[2,2] = 8.
Keep[2, 1] = 0 Vì không chọn bỏ Item 2 nào vào ba lô
Keep[2, 2] = 1 Vì chọn bỏ Item 2 vào ba lô
Keep[2, 3] = 0 Vì phần tử hiện hành là Item 2 không được chọn, chọn phần
tử trên nó V[1, 3] có giá trị cao hơn bỏ vào ba lô
Keep[2, 4] = 0 Vì tương tự như trên
Keep[2, 5] = 1 Vì có chọn bỏ Item 2 vào ba lô, sau đó vẫn còn trống 3 đơn
vị ta bỏ thêm V[1, 3] = 5 vào. Do đó ta giữ phương án này.
V[i,w] w=0
0
0
1
0
2
0
3

1
0
0
0

2
0
0
3



3
0
1
0

4
0
1
0

5
0
1
1

0
0
0
0

Đối với dòng thứ 4: Ta sử dụng cả 3 Item có giá trị
Item1 có v1 = 5 và w1 = 3 và Item2 có v2 = 3 và w2 = 2 và Item3 có v3 =
4 và w3 = 1
V[3, 1] = 4 Vì nó chỉ bỏ vừa Item 3 (v=4, w=1)
V[3, 2] = 4 Vì nó chỉ bỏ vừa Item 3
V[3, 3] = 7 Vì nó bỏ vừa Item 3(v=4, w=1), còn trống 2 đơn vị, có thể bỏ
thêm Item 2 (v=3, w=2). Và lớn hơn ô ở trên V[2, 3] = 5

6

0
3
4

3
0
5
5
7

4
0
5
5
9

5
0
5
8
9

Keep
0
1
2
3

1
0

0
0
0

Dựa vào mô tả ở trên ta có thể tính toán được tập hợp cấu thành phương
án tối ưu cho bài toán này.
Ta có n=3 và W=5
Xét Keep[3,5] = 1 do đó ta ta đưa Item 3 vào trong tập hợp T
Tiếp theo xét: Keep[3−1,W−w3] = Keep[2,4]
Keep[2, 4] = 0 do đó ta không đưa Item 2 vào tập hợp T. Sau đó xét
tiếp Keep[n−1,W−w3]=Keep[1,4] = 1 Do đó ta đưa Item 1 vào tập hợp T.
Cuối cùng ta thấy kết quả cuối cùng của bài toán xếp ba lô như sau:
Giá trị lớn nhất lấy được Vmax = 9 và T= {1,3}

7


CODE CHƯƠNG TRÌNH
#include <stdio.h>
#include <conio.h>
int main(int argc, char* argv[])
{
// khai bao bien
int w; // Khoi luong cua balo
int n; // So luong do vat cho vao balo
int KL[500]; // mang luu khoi luong cua cac do vat;
int GT[500]; // mang luu gia tri cua cac do vat;
int HamKetQua[500][500];
int i;// chỉ số chay theo số do vat : từ 0-->n
int j;// chỉ số chạy theo trọng lượng của balo : từ 0 --> w

}
while (KL[i]<1|| KL[i]>w);

9


// Phần này dùng để nhập mảng giá trị các túi
// Giá trị mỗi đồ vật phải >=1, nếu nhỏ hơn 1 sẽ nhập lại
do
{
printf("GT Dovat[%d]:=", i+1 );
scanf("%d", >[i]);
}
while (GT[i]