Bài Tập Qui hoạch động (Phụ lục đính kèm giáo trình)
Bài 1. Tam giác số
Dữ liệu vào : file văn bản TG.INP
-Dòng đầu số N :Chỉ số hàng của tam giác.
-N dòng tiếp theo, dòng thứ i chứa i số của hàng thứ i của tam giác
Kết qủa : Màn hình và file văn bản TG.OUT
-Dòng đầu chứa Tổng lớn nhất có được.
-Dòng tiếp theo các số trên đường đi và cách đi (T) trái , (P) phải.
Ví dụ :
TG.INP TG.OUT
5 30
7 7 T 3 T 8 P 7 T 5
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Bài 2. Dãy con chung
Vào : File văn bản DCC.INP
- Dòng đầu chứa hai số N, M (N, M ≤100 chỉ chiều dài của dãy a và dãy b)
- Các dòng tiếp theo chứa các số nguyên là các phần tử của dãy b ( a trước b sau) cácsố viết cách
nhau bởi ít nhất một dấu cách hoặc dấu xuống dòng.
Ra : File DCC.OUT và màn hình.
-Dòng đầu chứa số k chỉ số phần tử của dãy con chung.
-Các dòng tiếp theo chứa các phần tử của dãy con chung . Các số cách nhau ít nhất khoảng trắng
hoặc dấu xuống dòng.
Ví dụ :
DCC.INP DCC.OUT
7 6 4
3 5 2 3 5 5 3 2 5 3 2 5 5 3
5 3 1
Bài 3. “Phân Tích số “

,.......,a
n
và số nguyên dương k (k≤50).
Yêu cầu : Tìm dãy con nhiều phần tử nhất của dãy đã cho và có tổng các phần tử chia hết cho
k.
Dữ liệu vào: file văn bản DS.INP
-Dòng đầu tiên chứa hai số n, k viết các nhau ít nhất một dấu trắng
-Các dòng tiếp chứ các số a
1
, a
2
,.......,a
n
được ghi cách nhau bởi ít nhất một dấu trắng hoặc dấu xuống
dòng.
Kết qủa: Ghi ra file văn bản DS.OUT và ra màn hình.
-Dòng đầu tiên ghi m là số phần tử của dãy con tìm được.
-Các dòng tiếp theo ghi m chỉ số các phần tử của dãy đã cho có mặt trong dãy con tìm được. Các chỉ
số ghi cách nhau ít nhất một dấu trắng hoặc dấu xuống dòng
Ví dụ:
DS.INP DS.OUT
10 3 9
2 3 5 7 1 3 2 4 5
9 6 12 7 6 7 10 8
11 15
Bài 5. Chiếc Ba Lô.
Vào : File Text BALO.INP
-Dòng đầu tiên chưá hai số nguyên dương N,W (Số vật và khối lïng tối đa của ba lô) (N≤100,
W≤100)
-Các dòng tiếp theo chứa N cặp số a

2
các số viết cách nhau bởi ít nhất một dấu cách.
Xuất :
ra màn hình và file văn bản MBH.OUT dữ liệu như sau:
-Dòng đầu tiên : tiền lớn nhất thu được
-Dòng thứ hai : n
1
n
2
............. n
k
(n
i
là nước bán hàng lần thứ i)
-Dòng thứ ba : h
1
h
2
........... h
k
( hi là loại hàng bán tại nước i)
Các số viết cách nhau ít nhất một khoảng trống.
MBH.INP MBH.OUT
3 4 4
1 10 90
1 2 3 1 3 1 3 1
1 1 1 1 1 2 1 2
1 2 3 1
Bài 7. “Dãy Con tăng dần”.
Cho dãy N số nguyên dương a