Có reference từ bài viết về quy hoạch động của anh Nguyễn Đăng Quân (lamlaicuocdoi) smh

# Quy Hoạch Động là gì

Quy hoạch động là một phương pháp hiệu quả giải những bài toán tối ưu cấu hình hoặc bài toán đếm cấu hình mà bài toán ấy có ba tính chất sau đây:

- Bài toán lớn có thể phân rã thành những bài toán con đồng dạng
- Kết quả của các bài toán con có thể sử dụng để tìm ra lời giải tối ưu của bài toán lớn
- Hai bài toán con trong quá trình phân rã có thể có chung một số bài toán con khác

Tuy nhiên; chưa có một định lí nào khẳng định lớp bài toán có thể giải bằng quy hoạch động. Phương thức chủ yếu nhận dạng bài toán giải bằng QHĐ là bằng trải nghiệm/ kinh nghiệm trong quá trình làm bài

# QHĐ Knapsack

## Phát biều bài toán
Bài toán được phát biểu như sau:

"Cho $n$ sản phẩm; sản phẩm thứ $i$ có khối lượng là $w_{i}$ và mang giá trị là $v_{i}$, kí hiệu sản phẩm $i$ là $\left(w_{i}, v_{i}\right)$.

Cho một cái túi có chứa được tối đa cân nặng là $m$, hãy chọn ra một số sản phẩm cho vào cái túi sao cho tổng khói lượng của chúng không vượt quá $m$ và tổng giá trị của chúng là lớn nhất có thể."

## Phương thức giải
Ta thấy bài toán trên có thể phân rã thành những bài toán con có cùng khuôn dạng; thật vậy: Giả sử trong đáp án tối ưu, $\left(w_{i}, v_{i}\right)$ được cho vào túi; ta có thể bỏ qua $\left(w_{i}, v_{i}\right)$ và coi như chiếc túi có giới hạn trọng lượng là $m-w_{i} \Rightarrow$ Cách chọn các sản phẩm còn lại cũng phải là tối ưu.

Vậy ta đưa ra một thuật toán như sau:

Xét một cách chọn tối ưu sử dụng các sản phẩm $\left(w_{1}, v_{1}\right),\left(w_{2}, v_{2}\right), \ldots,\left(w_{i}, v_{i}\right)$; trong đó tổng khối lượng của các sản phẩm được cho vào balo là $SUM$. Ta gọi $f(i, SUM)$ là tổng giá trị của các sản phẩm được chọn trong phương án đó.

Các đồ vật ở trong túi lúc này có hai khả năng:

- Không chứa sản phẩm thứ $i$; trong trường hợp này, đáp án tối ưu là $f(i-1, SUM)$
- Có chứa sản phẩm thứ $i$; ta bỏ $\left(w_{i}, v_{i}\right)$ ra ngoài, cách chọn các sản phẩm còn lại cũng phải tối ưu là $f\left(i-1, SUM-w_{i}\right)$ Để cách chọn các sản phẩm là tối ư; ta cần chọn phương án tốt hơn, tức là:

$$
f(i, SUM)=\max \left\{f(i-1, SUM), f\left(i-1, SUM-w_{i}\right)\right\}
$$
Nhận xét: Mô hình trên vẫn đúng trong bài toán đếm; tức là với yêu cầu đếm số cách đặt sản phẩm vào ba lô sao cho tổng trọng lượng không quá $m$, khi ấy hàm mục tiêu biến đổi như sau:

- $\quad f(i, SUM)$ là số cách xếp sản phẩm vào ba lô sao cho tổng khối lượng là $SUM$
- Công thức truy hồi: $f(i, SUM)=f(i-1, SUM)+f\left(i-1, SUM-w_{i}\right)$

Từ công thức truy hồi ta suy ra hàm mục tiêu được cập nhật theo thứ tự tăng dần của giá trị thứ nhất và giá trị thứ hai; hay nói cách khác, $f(i, SUM)$ được cập nhật từ các giá trị mục tiêu $f\left(i^{\prime}, SUM^{\prime}\right)$ mà $i^{\prime} \leq i$ và $SUM^{\prime} \leq SUM$. Vì vậy $f\left(i^{\prime}, SUM^{\prime}\right)$ cần được tính toán trước $f(i, SUM)$ $\Rightarrow$ Ta cần duyệt $i$ tăng dần, đồng thời $SUM$ cũng duyệt tăng dần.

Pseudo code của bài toán có thể được viết như sau

for i from 1 to n
    for SUM = 0 to sum(all(w[1...i]))
        dp[i, SUM] = dp[i-1, SUM]
        if SUM >= w[i]
            dp[i, SUM] = max(dp[i, SUM], dp[i-1, SUM - w[i]] + v[i])

Mô hình trên cũng có thể áp dụng tương tự vào:
- Unbounded knapsack ([Link](https://www.geeksforgeeks.org/unbounded-knapsack-repetition-items-allowed/))
- Một số bài toán khác có ý tưởng tương tự

## Kết luận
Trong các bài toán quy hoạch động, có 2 công việc quan trọng cần phải thực hiện:

- Thứ nhất là tìm ra công thức truy hồi
- Thứ hai là tìm ra thứ tự duyệt

Đặc biệt trong các bài toán đếm càng cần phải cẩn thận về công thức và thứ tự duyệt. Khác với các bài toán tối ưu, một cấu hình được xét nhiều lần không làm giảm độ tốt của hàm mục tiêu; trong các bài toán đếm, nếu một cấu hình được xét nhiều lần sẽ dẫn đến tính thừa gây sai kết quả.

Chú ý: Trong một số bài toán về số học, tổng có thể biến thành tích (Tức là thay vì yêu cầu duy trì tổng các phần tử, đề yêu cầu duy trì tích các phần tử), song mô hình bài toán vẫn không thay đổi.

## Luyện tập
Không sắp xếp theo độ khó :>, nhưng những bài này khá basic
- https://cses.fi/problemset/task/1633
- http://thptchuyen.ntucoder.net/Problem/Details/9871
- http://vinhdinhcoder.net/Problem/Details/5156
- http://vinhdinhcoder.net/Problem/Details/5160
- http://vinhdinhcoder.net/Problem/Details/5157
- http://vinhdinhcoder.net/Problem/Details/5043
- http://vinhdinhcoder.net/Problem/Details/5197
- https://cses.fi/problemset/task/1636
- https://cses.fi/problemset/task/1635
- https://cses.fi/problemset/task/1634
- https://oj.vnoi.info/problem/bedao_m17_divisors
- https://codeforces.com/problemset/problem/1516/C
- https://oj.vnoi.info/problem/atcoder_dp_d
- https://oj.vnoi.info/problem/atcoder_dp_e