LOGO
TRƯỜNG ĐẠI HỌC SƯ PHẠM TPHCM
KHOA CÔNG NGHỆ THÔNG TIN
LỚP TIN HỌC KHÓA 35
BÁO CÁO BÀI TẬP LỚN
MÔN: CẤU TRÚC DỮ LIỆU 2
GVHD: ThS. NGUYỄN THỊ BÍCH NGÂN
THỰC HIỆN: NHÓM 25
NGUYỄN NGỌC NHẤT LINH
ĐINH VĂN QUYÊN
ĐỀ BÀI

Tên đề bài: Bố trí phòng họp.

Mô tả: Có n cuộc họp, cuộc họp thứ i bắt đầu
vào thời điểm si và kết thúc ở thời điểm fi.
Do chỉ có một phòng hội thảo nên 2 cuộc
họp bất kì sẽ được cùng bố trí phục vụ nếu
khoảng thời gian làm việc của chúng chỉ giao
nhau tại đầu mút. Hãy bố trí phòng họp để
phục vụ được nhiều cuộc họp nhất.
2
PHÂN TÍCH BÀI TOÁN

Giả sử ta có một tập S = {1, 2, …, n} gồm n cuộc
họp nhưng chỉ có 1 phòng hội thảo nên chỉ có
thể được dùng cho một cuộc họp tại một lúc.

Mỗi cuộc họp i có thời điểm bắt đầu si và một
thời điểm kết thúc fi, mà si ≤ fi. Nếu được lựa
chọn, cuộc họp i diễn ra trong thời khoảng [si, fi).

end
5
TỔ CHỨC DỮ LIỆU
int s[MAX];//lưu thời gian bắt đầu
cuộc họp
int f[MAX];//lưu thời gian kết thúc
cuộc họp
char *name[MAX];//Lưu tên khoa có
cuộc họp
int luu[MAX];//Lưu cuộc họp đã xếp
lịch
int n;//số cuộc họp có thể có
int dem=0;//lưu tổng số cuộc họp
hiện tại đã được bố trí
6
CÁC HÀM CHÍNH
void nhapDuLieuCuocHop();
void sapXep();//sắp xếp tăng theo
thời gian kết thúc
void boTriLichHop();
void xuatLichHop();
7
HÀM BỐ TRÍ LỊCH HỌP
void boTriLichHop()
{
//dem=0;
luu[dem]=0;
for(int i=1; i<n; ++i)
{
if(s[i]>=f[luu[dem]])

10
MỘT HƯỚNG ĐI KHÁC…

Giả sử dãy cuộc họp đã được sắp xếp tăng
dần theo thời gian kết thúc.

Hàm mục tiêu : y = độ dài dãy cuộc họp
được sắp

Gọi L(i) là độ dài dãy cuộc họp được sắp dài
nhất, các phần tử lấy trong miền từ 1 đến i
và phần tử cuối cùng là i.
11
1
2 3 … i i+1
Dãy cuộc họp
PP QUY HOẠCH ĐỘNG

Nhận xét: Với cách làm này ta đã chia 1 bài
toán lớn (dãy con của n cuộc họp) thành các
bài toán con cùng kiểu có kích thước nhỏ
hơn (dãy con của dãy có i cuộc họp đầu
tiên). Vấn đề là công thức truy hồi để phối
hợp kết quả của các bài toán con.
12
PP QUY HOẠCH ĐỘNG

Ta có công thức QHĐ để tính L(i) như sau:

L(0) = 1. (Hiển nhiên)

14
TẠO BẢNG

TH riêng đơn giản nhất: khi i=0:

L[0]=1 (hiển nhiên)

truoc[0]=-1

TH i>0:

Đặt LMax={L[j]: f[j]<=s[i], 0<=j<i}

L[i]=LMax+1;

truoc[i]=j tương ứng khi tìm thấy LMax
15
TẠO BẢNG

Ví dụ:
16
i 0 1 2 3 4 5 6 7
s[i] 1 4 3 12 11 10 14 27
f[i] 3 6 9 13 18 22 27 31
L[i] 1 2 2 3 3 3 4 5
truoc[i] -1 0 0 1 1 1 3 6
TẠO BẢNG

HÀM TẠO BẢNG
void taoBangLichHop()

18
i s[i] f[i] truoc[i]
7 27 31 6
6 14 27 3
3 12 13 1
1 4 6 0
0 1 3 -1
Dừng
TRA BẢNG

HÀM TRA BẢNG:
void traBangLichHop()
{
int i=0;
for(int j=1; j<n; ++j)
if(L[i]<L[j])
i=j;
int max=y=L[i]-1;//i la chi so co L[i] lon nhat
// vi mang trong C++ bat dau tu 0 nen phai -1
while(i>-1)
{
luu[max ]=i;
i=truoc[i];
}
}
19
NHẬN XÉT

Giải thuật Quy hoạch động có ưu thế hơn giải
thuật Quay lui khi biết lợi dụng những bài