KHOA CÔNG NGHỆ THÔNG TIN
MÔN: PHÂN TÍCH ĐÁNH GIÁ THUẬT TOÁN

BÀI TẬP LỚN

ĐỀ TÀI: Phương pháp quy hoạch động. Giải bài toán ba lô không hạn chế:
cho n loại đồ vật có khối lượng w1, ..., wn và có giá trị v1, ..,vn. Xếp đồ vật vào
ba lô có sức chứ T sao cho tổng giá trị lớn nhất. Giả thiết T, wi, vi, i=1,..,n, đều
là các số nguyên dương.

Giáo viên hướng dẫn

: Đào Thanh Tĩnh

Sinh viên thực hiện

: Lê Hoàng Phương - 13870819

Lớp

: HTTT3 - K25B

Hà Nội, 28 tháng 5 năm 2014


Bài toán ba lô không giới hạn

GIỚI THIỆU
Bài toán xếp ba lô (còn có tên gọi là bài toán cái túi) là một bài toán tối ưu hóa
tổ hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể nhét
vừa vào trong một cái ba lô(với giới hạn khối lượng) để mang theo trong một

Nguyên lý tối ưu Bellman
- Quy hoạch động là quá trình điểu khiển tối ưu với trạng thái bắt đầu. Mọi trạng
thái A bất kỳ thuộc quá trình này cũng tối ưu.
- Tư tưởng chính: Thực hiện các bài toán con trước, sử dụng các kết quả này để
giải bài toán lớn
- Hướng tiếp cận:
+ Giải bài toán theo công thức truy hồi
+ Giải các bài toán con trước
+ Dựa vào bài toán con để giải bài toán lớn hơn cho đến khi gặp bài toán
cần giải
- Tổng quát:
+ Giải bài toán qua N bước
+ Giải bài toán sao cho tổng chi phí 1 -> N-1 và từ N-1 -> N là tối ưu
Thuật toán quy hoạch động
Bước 1: Xây dựng công thức truy hồi
Giả sử: Chia bài toán thành N giai đoạn 1->N
Xác định F(1) - cơ sở quy nạp
- Gọi (i) là hàm số xác định giá trị tối ưu, tính đến giá trị thứ i
-> F(n) là nghiệm của bài toán
- Đối với bài toán
+ Tìm Min: F(N) = Min{F(i), F(j)}
i = 1, N-1
j = N-1, N
12/13


Bài toán ba lô không giới hạn

+ Tìm Max: F(N) = Max{F(i), F(j)}
i = 1, N-1


•

Có 1 ba lô với sức chứa T:

12/13


Bài toán ba lô không giới hạn

•

Vấn đề:
Xếp đồ vật vào ba lô có sức chứ T sao cho tổng giá trị lớn
nhất. Giả thiết T, wi, vi, i=1,..,n, đều là các số nguyên
dương.

Giải quyết bài toán trong trường hợp sau: Mỗi vật được chọn nhiều lần (không
hạn chế số lần)
Ví dụ:
12/13


Bài toán ba lô không giới hạn

InputData: file văn bản Bag.inp
Dòng 1: n, T cách nhau ít nhất một dấu cách
n dòng tiếp theo: Mỗi dòng gồm 2 số Wi, Vi, là chi phí và giá trị đồ vật
thứ i.
OutputData: file văn bản bag.out: Ghi giá trị lớn nhất tên trộm có thể lấy


Sơ đồ:
Bước chia: tạo nên 1 vấn đề nhỏ được giải quyết và có thể hỗ trợ giải quyết bài
toán gốc.

12/13


Bài toán ba lô không giới hạn

Mỗi 1 bài toán con giải quyết sẽ quay trở lại hỗ trợ giải quyết bài toán gốc:

12/13


Bài toán ba lô không giới hạn

Bước lấp đầy các phương án và Truy vết:

Ta nhận thấy: sẽ có k >= 1 đồ vật được sắp xếp vào bao lô nếu T >= Wi
Định nghĩa:
M(v[], w[], T) = là giá trị lớn nhất của: v1×x1 + v2×x2 + ... + vN×xN
subject to: w1×x1 + w2×x2 + ... + wN×xN ≤ T
Tường hợp cơ sở của bài toán ba lô – không giới hạn:
Khi Ba lô đầy, không thể sắp xếp bất kỳ 1 vật nào vào túi. Bởi vì, tổng giá
trị của ba lô lúc đó = 0. Hay: M(v, w, 0) = 0; (Không thể sắp xếp bất kỳ thứ gì
vào túi ba lô không có sứ chứa).
3.2. Bảng phương án
Ta xây dựng bảng phương án dựa trên công thức truy hồi trên. Để kiểm tra kết
quả có chính xác hay không (nếu không chính xác chúng ta xây dựng lại hàm

M( v[], w[], C )
{
int[] sol, mySol, myFinalSol;
/* ==============================================
Chia nhỏ bài toán để giải quyết
============================================== */
/* ---------------------------------------------Giải quyết những bài toán nhỏ dễ giải quyết hơn
---------------------------------------------- */
for ( i = 1; i ≤ N; i++ )
{
if ( C ≥ w[i] )
sol[i] = M( v, w, C-w[i] );
// Sức chứa ba lô giảm w[i] vì đồ vật thứ i được xếp ở trong túi
else
sol[i] = 0;
// không đủ chứa vật thứ i
}
/* ----------------------------------------------------------------Sử dụng giải pháp của các bài toản nhỏ để giải quyết bài toán gốc
-------------------------------------------------------------- */
for ( i = 1; i ≤ N; i++ )
{
if ( C ≥ w[i] )
mySol[i] = sol[i] + v[i];
// Giá trị cân nặng ba lô tăng thêm v[i]vì đồ vật thứ I được xếp trong túi
else
mySol[i] = 0;
// không đủ chứa vật thứ i
}
/* *************************
Tìm giá trị tốt nhất (maximum)

12/13