---
title:
Quy hoạch động (Phần 3: Quy hoạch động knapsack)
---

Quy hoạch động (Phần 3: Quy hoạch động knapsack)
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

# Kiến thức cần có
Để hiểu hơn về **Quy hoạch động cái túi (knapsack)**, trước hết bạn hãy tìm hiểu:
- Kĩ thuật [Quy hoạch động](https://hackmd.io/@2SchoolGuideline/r1PSIpVcT)
- Kĩ thuật [Đệ quy và quay lui](https://hackmd.io/zq12mu3IScqbYy9a9HtSRw)

# Quy hoạch động cái túi (knapsack)
## 1. Bài toán
Có $n$ đồ vật được đánh số từ $1$ đến $n$. Đồ vật thứ $i$ $(1 \le i \le n)$ có khối lượng $w_i$ và giá trị $v_i$. Có một chiếc túi có sức chứa tối đa là $W$ - tổng khối lượng tối đa của các vật đựng trong túi là $W$. Biết mỗi đồ vật chỉ được chọn một lần. Tính tổng giá trị $V$ lớn nhất của các đồ vật đựng trong túi. (Giả sử chọn cách đánh số mảng bắt đầu từ $1$)

## 2. Thuật toán
Với bài toán này, chúng ta cần quan tâm tới các yếu tố:
- **Đồ vật thứ bao nhiêu (1)**
- **Tổng khối lượng các đồ vật (2)**
- **Tổng giá trị các đồ vật (3)**

Ta sẽ chọn 1 trong số 3 yếu tố này để tính toán, và sử dụng 2 yếu tố còn lại làm trạng thái quy hoạch động. Ta nhận thấy, để thuận lợi trong việc giải bài toán này, nên lựa chọn tính theo **(2)** hoặc **(3)**.

### 2.1. Cách 1 (tính theo (3))
- **Sử dụng:** Bài toán có giới hạn $n * W$ vừa đủ chạy trong thời gian cho phép.
- **Gọi** `dp[i][x]` là tổng giá trị lớn nhất của túi khi xét từ vật 1 đến vật `i` và tổng trọng lượng các vật trong túi chưa vượt quá `x`.
- **Trường hợp suy biến:**
- `dp[i][0] = 0`
- `dp[0][x] = 0`
- **Công thức truy hồi:**
- **Nếu** `w[i] > x` *Không* chọn vật thứ `i` => `dp[i][x] = dp[i - 1][x]`
- **Nếu** `w[i] <= x`, ta có 2 lựa chọn:
- Chọn vật thứ `i` => Cần lấy từ `i - 1` vật còn lại sao cho tổng khối lượng của chúng không vượt quá `x - w[i]`: `dp[i - 1][x - w[i]] + v[i]`
- *Không* chọn vật thứ `i` => Cần lấy từ `i - 1` vật còn lại sao cho tổng của chúng không vượt quá `x`: `dp[i - 1][x]`
$\Rightarrow$ **Phương án tối ưu:** Chọn cách cho ra giá trị lớn hơn trong 2 cách nêu trên: `dp[i][x] = max(dp[i - 1][x - w[i]] + v[i], dp[i - 1][x])`
- **Đáp số:** `dp[n][W]`
- **Độ phức tạp thời gian:** $O(n * W)$
- **Luyện tập cách cài đặt:** [Atcoder Educational DP Contest D - Knapsack 1](https://oj.vnoi.info/problem/atcoder_dp_d)

:::spoiler **Code mẫu**:

#include<bits/stdc++.h>
using namespace std;

int n;
long long W;
long long w[102];
long long v[102];
long long dp[102][100002];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> W;
    for(int i = 1; i <= n; ++i) cin >> w[i] >> v[i];

    for(int i = 1; i <= n; ++i) dp[i][0] = 0;
    for(int x = 0; x <= W; ++x) dp[0][x] = 0;

    for(int i = 1; i <= n; ++i){
        for(int x = 1; x <= W; ++x){
            if(w[i] > x) dp[i][x] = dp[i - 1][x];
            else dp[i][x] = max(dp[i - 1][x - w[i]] + v[i], dp[i - 1][x]);
        }
    }

    cout << dp[n][W];
}

:::

- Tối ưu 1 chiều:
- **Gọi** `dp[x]` là tổng giá trị lớn nhất của túi khi tổng khối lượng là `x`.
- **Trường hợp suy biến:**
- `dp[0] = 0`
- **Công thức truy hồi:**
- Lặp biến i từ $1$ đến $n$. Trong mỗi lần lặp $i$, chạy biến $x$ từ $W$ đến $1$ (tránh trường hợp trùng lắp): `dp[x] = max(dp[x], dp[x - w[i]] + v[i])` (nếu $w[i] \le x$)
:::spoiler **Tại sao lại duyệt x từ W đến 1?**
Với giá trị i bất kì từ 1 -> n:
- Giả sử đang xét đến x => đã cập nhật dp[0] -> dp[x - 1] (có thể có hoặc không chứa vật thứ i).
- Nếu cập nhật dp[x] cho i dựa trên giá trị từ dp[0] -> dp[x - 1] thì có khả năng dùng đồ vật i 2 lần.
=> Nếu chạy ngược về thì khi xét đến dp[x] thì dp[0] -> dp[x - 1] chỉ mới được tính cho đồ vật thứ i - 1 => không chứa đồ vật thứ i.
:::

- **Đáp số:** `dp[W]`

:::spoiler **Code mẫu**:

int n;
long long W;

long long w[102];
long long v[102];

long long dp[100002];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> W;
    for(int i = 1; i <= n; ++i) cin >> w[i] >> v[i];

    for(int x = 0; x <= W; ++x) dp[x] = 0;

    for(int i = 1; i <= n; i++){
        for(int x = W; x >= 1; --x){
            if(w[i] <= x) dp[x] = max(dp[x], dp[x - w[i]] + v[i]);
        }
    }

    cout << dp[W];

}

:::
### 2.2. Cách 2 (tính theo (2))
- **Sử dụng:** Bài toán có giới hạn $n * W$ lớn, nếu dùng cách 1 sẽ bị quá thời gian, tuy nhiên, $n * V$ (với $V$ là tổng các giá trị $v[i]$) lại vừa đủ chạy trong giới hạn thời gian cho phép.
- **Gọi** `dp[i][y]` là tổng khối lượng nhỏ nhất khi xét từ vật 1 đến vật `i` để đạt được giá trị `y`, $V$ là tổng các giá trị $v[i]$.
- **Trường hợp suy biến:**
- `dp[0][0] = 0`
- `dp[i][0] = 0`
- `dp[i][j] = INF` (với ô [i][j] chưa được gán ở 2 bước trên và INF là giá trị rất lớn (thường >= $10^{18}$ ))
- **Công thức truy hồi:**
- **Nếu** `v[i] > y` *Không* chọn vật thứ i => `dp[i][y] = dp[i - 1][y]`
- **Nếu** `v[i] <= y`, ta có 2 lựa chọn:
- Chọn vật thứ `i` => Cần lấy từ `i - 1` vật còn lại sao cho tổng giá trị của chúng không vượt quá `y - v[i]`: `dp[i - 1][y - v[i]] + w[i]`
- *Không* chọn vật thứ `i` => Cần lấy từ `i - 1` vật còn lại sao cho tổng giá trị của chúng không vượt quá `y`: `dp[i - 1][y]`
=> **Phương án tối ưu:** Chọn cách cho ra tổng khối lượng nhỏ hơn trong 2 cách nêu trên (do tổng khối lượng nhỏ hơn đảm bảo khó vượt qua giới hạn túi hơn): `dp[i][y] = min(dp[i - 1][y - v[i]] + w[i], dp[i - 1][y])`
- **Đáp số:** Lặp biến j từ 1 đến V. Với mỗi giá trị j, ta lặp tìm `min(dp[i][j])` (với i từ 1 -> n). Đáp số của bài toán là giá trị j lớn nhất mà `min(dp[i][j]) <= W`.
- **Độ phức tạp thời gian:** $O(n * V)$
- **Luyện tập cách cài đặt:** [Atcoder Educational DP Contest E - Knapsack 2](https://oj.vnoi.info/problem/atcoder_dp_e)
:::spoiler **Code mẫu**:

#include<bits/stdc++.h>
using namespace std;

int n;
long long W;
long long V;
const long long INF = 1000000000000000000;
long long w[102];
long long v[102];
long long dp[102][100002];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> W;
    for(int i = 1; i <= n; ++i) cin >> w[i] >> v[i];
    for(int i = 1; i <= n; ++i) V += v[i];

    for(int i = 0; i <= n; ++i) {
        for(int y = 1; y <= V; ++y)
            dp[i][y] = INF;
    }
    for(int y = 1; y <= V; ++y){
        for(int i = 1; i <= n; ++i){
            if(v[i] > y) dp[i][y] = dp[i - 1][y];
            else dp[i][y] = min(dp[i - 1][y - v[i]] + w[i], dp[i - 1][y]);
        }
    }

    long long ans = 0;
    for(int j = 1; j <= V; ++j){
        long long mn = INF;
        for(int i = 1; i <= n; ++i) mn = min(mn, dp[i][j]);
        if(mn <= W) ans = j;
    }

    cout << ans;
}

:::

- Tối ưu 1 chiều:
- **Gọi** `dp[y]` là tổng khối lượng bé nhất của túi khi tổng giá trị là `y`.
- **Trường hợp suy biến:**
- `dp[0] = 0`
- `dp[i] = INF`
- **Công thức truy hồi:**
- Lặp biến i từ 1 đến n. Trong mỗi lần lặp i, chạy biến y từ V đến 1 (tránh trường hợp trùng lắp): `dp[y] = min(dp[y], dp[y - v[i]] + w[i])` (nếu v[i] <= y)
- **Đáp số:** Lặp biến j từ 1 đến V. Đáp số của bài toán là giá trị j lớn nhất mà `dp[j] <= W`.
:::spoiler **Code mẫu**:

#include<bits/stdc++.h>
using namespace std;

int n;
long long W;
long long V;
const long long INF = 1000000000000000000;
long long w[102];
long long v[102];
long long dp[100002];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> W;
    for(int i = 1; i <= n; ++i) cin >> w[i] >> v[i];
    for(int i = 1; i <= n; ++i) V += v[i];

    for(int i = 1; i <= V; i++) dp[i] = INF;
    dp[0] = 0;

    for(int i = 1; i <= n; ++i){
        for(int y = V; y >= 1; --y){
            if(v[i] <= y) dp[y] = min(dp[y], dp[y - v[i]] + w[i]);
        }
    }

    long long ans = INF;
    for(int j = 1; j <= V; ++j){
        if(dp[j] <= W) ans = j;
    }

    cout << ans;
}

:::
# Bài tập vận dụng
Các bài tập dưới đây ứng dụng các ý tưởng và công thức truy hồi ở trên và chúng không nhất thiết phải liên quan đến "cái túi".
## [CSES - Minimizing Coins](https://cses.fi/problemset/task/1634)
### Đề bài
Một hệ thống tiền xu có $n$ mệnh giá ($1 \le n \le 100$), mệnh giá thứ $i$ là $c_i$ ($1 \le i \le n$, $1 \le c_i \le 10^6$). Tìm cách để tạo ra số tiền $x$ ($1 \le x \le 10^6$) sao cho số đồng xu được sử dụng là ít nhất.
#### Input
- Dòng đầu tiên gồm $n$ và $x$ ($1 \le n \le 100$, $1 \le x \le 10^6$)
- Dòng tiếp theo gồm $n$ giá trị $c_i$ ($1 \le i \le n$, $1 \le c_i \le 10^6$)
#### Output
- Một dòng duy nhất là số đồng xu ít nhất để tạo ra được số tiền $x$. Nếu không có cách nào để tạo ra được số tiền $x$ thì in ra `-1`
#### Sample Input

3 11
1 5 7

#### Sample Output

3

#### Giải thích
Cách để tạo ra số tiền là `11` mà sử dụng ít đồng xu nhất là: sử dụng `2` đồng xu mệnh giá `5` và `1` đồng xu mệnh giá `1`, tổng cộng `3` đồng xu.

## [CSES - Coin Combinations I](https://cses.fi/problemset/task/1635)
### Đề bài
Một hệ thống tiền xu có $n$ mệnh giá ($1 \le n \le 100$), mệnh giá thứ $i$ là $c_i$ ($1 \le i \le n$, $1 \le c_i \le 10^6$). Tính số cách khác nhau *(hai cách **sử dụng những đồng tiền giống nhau** nhưng **thứ tự sử dụng khác nhau** được coi là **khác nhau**)* để tạo ra số tiền $x$ ($1 \le x \le 10^6$) modulo $10^9+7$.
#### Input
- Dòng đầu tiên gồm $n$ và $x$ ($1 \le n \le 100$, $1 \le x \le 10^6$)
- Dòng tiếp theo gồm $n$ giá trị $c_i$ ($1 \le i \le n$, $1 \le c_i \le 10^6$)
#### Output
- Một dòng duy nhất là số cách khác nhau để tạo ra số tiền $x$ modulo $10^9+7$.
#### Sample Input

3 9
2 3 5

#### Sample Output

8

#### Giải thích
`8` cách để tạo ra số tiền là `9` như sau:
1. `2+2+5`
2. `2+5+2`
3. `5+2+2`
4. `3+3+3`
5. `2+2+2+3`
6. `2+2+3+2`
7. `2+3+2+2`
8. `3+2+2+2`

## [CSES - Coin Combinations II](https://cses.fi/problemset/task/1636)
### Đề bài
Một hệ thống tiền xu có $n$ mệnh giá ($1 \le n \le 100$), mệnh giá thứ $i$ là $c_i$ ($1 \le i \le n$, $1 \le c_i \le 10^6$). Tính số cách khác nhau *(hai cách **sử dụng những đồng tiền giống nhau** được coi là **giống nhau**, cho dù **thứ tự sử dụng khác nhau**)* để tạo ra số tiền $x$ ($1 \le x \le 10^6$) modulo $10^9+7$.
#### Input
- Dòng đầu tiên gồm $n$ và $x$ ($1 \le n \le 100$, $1 \le x \le 10^6$)
- Dòng tiếp theo gồm $n$ giá trị $c_i$ ($1 \le i \le n$, $1 \le c_i \le 10^6$)
#### Output
- Một dòng duy nhất là số cách khác nhau để tạo ra số tiền $x$ modulo $10^9+7$.
#### Sample Input

3 9
2 3 5

#### Sample Output

3

#### Giải thích
`3` cách để tạo ra số tiền là `9` như sau:
1. `2+2+5`
2. `3+3+3`
3. `2+2+2+3`

## Bài tập thêm
- [AtCoder - abc321F](https://atcoder.jp/contests/abc321/tasks/abc321_f)
- [Codeforces - 687C](https://codeforces.com/contest/687/problem/C)
- [Codeforces - 1862F](https://codeforces.com/contest/1862/problem/F)

# Hướng dẫn tự học

| Bước | Nội dung chi tiết |
|:----:|:--------------------------------------------------------------------------------------------------------------------------------------- |
| 1 | - Đọc tài liệu thật kĩ để hiểu nội dung.<br>- Khi gặp bài toán: thử dành vài phút đọc đề, viết ý tưởng ra nháp, suy nghĩ trước khi xem lời giải. |
| 2 | - Giải bài tập dựa trên lý thuyết, suy nghĩ đưa về hướng giải của các bài quen thuộc.<br>- Xem ý tưởng và cách cài đặt (nếu cần).

# Nguồn tham khảo
[2SG - LCS + Knapsack](https://hackmd.io/@hphuong/Bya-QW-H3)
[Bài toán cái túi và những ứng dụng xung quanh nó](https://viblo.asia/p/bai-toan-cai-tui-va-nhung-ung-dung-xung-quanh-no-maGK7Nke5j2)
[Quy hoạch động cơ bản](https://vnoi.info/wiki/algo/dp/basic-dynamic-programming-1.md)