DATA STRUCTURE AND ALGORITHM
Dynamic Programming

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Qui hoạch động
Dr. Dao Nam Anh

Data Structure and Algorithm

1


Resource - Reference
Slides adapted from James B D Joshi,
edit by Dao Nam Anh.
Major Reference:

•

Robert Sedgewick, and Kevin Wayne,
“Algorithms” Princeton University, 2011, Addison
Wesley

•

Algorithm in C (Parts 1-5 Bundle)- Third Edition
by Robert Sedgewick, Addison-Wesley

•
•

Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường.
Giải thuật và lập trình, Lê Minh Hoàng, Đại Học
Sư Phạm, 2002
Data Structure and Algorithm

2


Divide and Conquer
Chia và Trị

•

Một số chương trình đệ qui gọi chính nó cho hai
tập dữ liệu có kích thước ½
 Chia vấn đề này thành 2 phần và thực hiện từng
phần

•
•

Chi phí thời gian: TN = Tk + TN-k + 1

Many recursive programs use recursive calls on two subsets of inputs
(two halves usually)
 Divide the problem and solve them – divide and conquer paradigm
 Complexity: TN = Tk + TN-k + 1

Data Structure and Algorithm


3


Find max- Divide and Conquer
Tìm số lớn nhất – theo cách chia và trị
2 317

Item max(Item a[], int l, int r)
{ Item u, v;
int m = (l+r)/2;
if (l == r) return a[l];
u = max(a, l, m);
v = max(a, m+1, r);
if (u > v) return u;
else return v;
}

Data Structure and Algorithm

4


Find max- Divide and Conquer
Tìm số lớn nhất – theo cách chia và trị
1

2 317
2

2 3


1 7

Item max(Item a[], int l, int r)
{ Item u, v;
int m = (l+r)/2;
if (l == r) return a[l];
u = max(a, l, m);
v = max(a, m+1, r);
if (u > v) return u;
else return v;
}

Data Structure and Algorithm

5


Find max- Divide and Conquer
Tìm số lớn nhất – theo cách chia và trị
1

2 317
2

2 3

1 7

3


2

3

Item max(Item a[], int l, int r)
{ Item u, v;
int m = (l+r)/2;
if (l == r) return a[l];
u = max(a, l, m);
v = max(a, m+1, r);
if (u > v) return u;
else return v;
}

Data Structure and Algorithm

6


Find max- Divide and Conquer
Tìm số lớn nhất – theo cách chia và trị
1

2 317
2

2 3

1 7


3
4
2

2

3

Item max(Item a[], int l, int r)
{ Item u, v;
int m = (l+r)/2;
if (l == r) return a[l];
u = max(a, l, m);
v = max(a, m+1, r);
if (u > v) return u;
else return v;
}

Data Structure and Algorithm

7


Find max- Divide and Conquer
Tìm số lớn nhất – theo cách chia và trị
1

2 317
2


2 3

1 7

3
4
2

2

5

3

Item max(Item a[], int l, int r)
{ Item u, v;
int m = (l+r)/2;
if (l == r) return a[l];
u = max(a, l, m);
v = max(a, m+1, r);
if (u > v) return u;
else return v;
}

Data Structure and Algorithm

8



Find max- Divide and Conquer
Tìm số lớn nhất – theo cách chia và trị
1

2 317
2

2 3
3
4
2

2

1 7
6

5

3

3

Item max(Item a[], int l, int r)
{ Item u, v;
int m = (l+r)/2;
if (l == r) return a[l];
u = max(a, l, m);
v = max(a, m+1, r);
if (u > v) return u;

else return v;
}

Data Structure and Algorithm

9


Find max- Divide and Conquer
Tìm số lớn nhất – theo cách chia và trị
1

2 317
2

7
3

2 3
3
4
2

2

1 7
6

5


3

3

Item max(Item a[], int l, int r)
{ Item u, v;
int m = (l+r)/2;
if (l == r) return a[l];
u = max(a, l, m);
v = max(a, m+1, r);
if (u > v) return u;
else return v;
}

Data Structure and Algorithm

10


Find max- Divide and Conquer
Tìm số lớn nhất – theo cách chia và trị
1

2 317
2

7

8


3

2 3
3
4
2

2

1 7
6

5

3

3

Item max(Item a[], int l, int r)
{ Item u, v;
int m = (l+r)/2;
if (l == r) return a[l];
u = max(a, l, m);
v = max(a, m+1, r);
if (u > v) return u;
else return v;
}

Data Structure and Algorithm


11


Find max- Divide and Conquer
Tìm số lớn nhất – theo cách chia và trị
1

2 317
2

7

8

3

2 3
3
4
2

2

1 7
6

9

5


3

3

1

7

Item max(Item a[], int l, int r)
{ Item u, v;
int m = (l+r)/2;
if (l == r) return a[l];
u = max(a, l, m);
v = max(a, m+1, r);
if (u > v) return u;
else return v;
}

Data Structure and Algorithm

12


Find max- Divide and Conquer
Tìm số lớn nhất – theo cách chia và trị
1

2 317
2


7

8

3

2 3
3
4
2

2

1 7
6

9

5

3

3

1

10
1

7


Item max(Item a[], int l, int r)
{ Item u, v;
int m = (l+r)/2;
if (l == r) return a[l];
u = max(a, l, m);
v = max(a, m+1, r);
if (u > v) return u;
else return v;
}

Data Structure and Algorithm

13


Find max- Divide and Conquer
Tìm số lớn nhất – theo cách chia và trị
1

2 317
2

7

8

3

2 3

3
4
2

2

1 7
6

9

5

3

3

1

10
11
1

12
7

7

Item max(Item a[], int l, int r)
{ Item u, v;

int m = (l+r)/2;
if (l == r) return a[l];
u = max(a, l, m);
v = max(a, m+1, r);
if (u > v) return u;
else return v;
}

Data Structure and Algorithm

14


Find max- Divide and Conquer
Tìm số lớn nhất – theo cách chia và trị
1

2 317
2

7

13

8

3

7


2 3
3
4
2

2

1 7
6

9

5

3

3

1

10
11
1

12
7

7

Item max(Item a[], int l, int r)

{ Item u, v;
int m = (l+r)/2;
if (l == r) return a[l];
u = max(a, l, m);
v = max(a, m+1, r);
if (u > v) return u;
else return v;
}

Data Structure and Algorithm

15


Find max- Divide and Conquer
Tìm số lớn nhất – theo cách chia và trị
7
1

1

2 317
2

7

13

8


3

7

2 3
3
4
2

2

1 7
6

9

5

3

3

1

10
11
1

12
7


7

Item max(Item a[], int l, int r)
{ Item u, v;
int m = (l+r)/2;
if (l == r) return a[l];
u = max(a, l, m);
v = max(a, m+1, r);
if (u > v) return u;
else return v;
}

Data Structure and Algorithm

16


Dynamic programming
Qui hoạch động

•

•

Các thuật toán đệ quy có ưu điểm dễ cài đặt,
tuy nhiên do bản chất của quá trình đệ quy,
các chương trình này thường kéo theo những
đòi hỏi lớn về không gian bộ nhớ và một khối
lượng tính toán khổng lồ.

Quy hoạch động (Dynamic programming) là
một kỹ thuật nhằm đơn giản hóa việc tính toán
các công thức truy hồi bằng cách lưu trữ toàn
bộ hay một phần kết quả tính toán tại mỗi
bước với mục đích sử dụng lại.
Data Structure and Algorithm

17


Dynamic programming
Qui hoạch động

•
•

•

Bản chất của quy hoạch động là thay thế mô hình tính
toán “từ trên xuống” (Top-down) bằng mô hình tính
toán “từ dưới lên” (Bottom-up).
Từ “programming” ở đây không liên quan gì tới việc
lập trình cho máy tính, đó là một thuật ngữ mà các
nhà toán học hay dùng để chỉ ra các bước chung
trong việc giải quyết một dạng bài toán hay một lớp
các vấn đề.
Không có một thuật toán tổng quát để giải tất cả các
bài toán quy hoạch động.
Data Structure and Algorithm


18


Dynamic programming
Qui hoạch động

•

•

Phép phân giải đệ quy bắt đầu từ bài toán lớn phân
rã thành nhiều bài toán con và đi giải từng bài toán
con đó. Việc giải từng bài toán con lại đưa về phép
phân rã tiếp thành nhiều bài toán nhỏ hơn và lại đi giải
tiếp bài toán nhỏ hơn đó bất kể nó đã được giải hay
chưa.
Quy hoạch động bắt đầu từ việc giải tất cả các bài
toán nhỏ nhất ( bài toán cơ sở) để từ đó từng bước
giải quyết những bài toán lớn hơn, cho tới khi giải
được bài toán lớn nhất (bài toán ban đầu).
Data Structure and Algorithm

19


Dynamic programming
Knapsack problem - Bài toán Cái túi
•

Trong siêu thị có n gói hàng, các gói hàng có

trọng lượng khác nhau W[i], có giá trị khác nhau
V[i]. 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.

•

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.

•

Knapsack problem
 Given
» N types of items of varying size and value
» One knapsack (belongs to a thief!)

Data Structure and Algorithm

 Find: the combination of items that maximize the total value

20


Dynamic programming
Knapsack problem - Bài toán Cái tú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 được chọn trong số

n gói với giới hạn trọng lượng M chính
là F[n, M].

Data Structure and Algorithm

21


Dynamic programming
Knapsack problem - Bài toán Cái túi
Với giới hạn trọng lượng j, việc chọn tối ưu
trong số các gói {1, 2, …, i - 1, i} để có giá trị
lớn nhất sẽ có hai khả năng:
a. Nếu không chọn gói thứ i thì F[i, j] là giá trị
lớn nhất có thể 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 là
j. Tức là
F[i, j] = F[i - 1, j]
Data Structure and Algorithm

22


Dynamic programming
Knapsack problem - Bài toán Cái túi
b. Nếu có chọn gói thứ i (chỉ xét tới 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ể,
nên F[i, j] sẽ là max trong 2 giá trị thu được ở trên.

Data Structure and Algorithm

23


Dynamic programming
Knapsack problem - Bài toán Cái túi
Knapsack size: 17

0 1 2 3

4

Item

A B C

D E

Size

3 4 7

8 9

Val


4 5 10 11 13

int knap(int cap)
{ int i, space, max, t;
for (i = 0, max = 0; i < N; i++)
if ((space = cap - items[i].size) >= 0)
if ((t = knap(space) + items[i].val) > max)
max = t;
return max;
}

int knap(int M)
{ int i, space, max, maxi, t;
if (maxKnown[M] != unknown) return maxKnown[M];
for (i = 0, max = 0; i < N; i++)
if ((space = M-items[i].size) >= 0)
if ((t = knap(space) + items[i].val) > max) { max = t; maxi = i; }
maxKnown[M] = max; itemKnown[M] = items[maxi];
return max; }
Data Structure and Algorithm

24


Discussion – Câu hỏi

•

/>

Data Structure and Algorithm

25