Áp dụng phương pháp "FAST" để giải quyết các bài toán quy hoạch động (Tiếp theo)

Trong bài viết này mình sẽ trình bày một ví dụ khác phức tạp hơn sử dụng phương pháp FAST để làm bài toán quy hoạch động. Nếu chưa đọc phần 1 trong seri này về phương pháp FAST, bạn có thể đọc bài viết đó tại link này: Giải quyết quy hoạch động bằng phương pháp FAST.
Bài toán ví dụ Knapsack điển hình:
Giả sử có một cái túi chỉ chứa được tối đa M(đơn vị khối lượng), có một đống gold mỗi cục có khối lượng là w và giá trị là v. Nhiệm vụ là chọn cục nào để tổng giá trị là lớn nhất nhưng tổng khối lượng phải nhỏ hơn hoặc bằng M.
VD:
input:
cục 1 (w:2, v:6), cục 2 (w:2, v:10), cục 3 (w:3, v:12)} M = 5
output:
22
Giải thích: Ta sẽ chọn cục 2 và 3 có tổng khối lượng là 5 <= M và tổng giá trị là lớn nhất = 22

2.1 First solution

Như thường lệ ta sẽ giải quyết bài toán này bằng phương pháp “ngây thơ” trước bằng đệ quy