---
title
Quy hoạch động (Phần 3) - Lời giải
---
Quy hoạch động (Phần 3) - Lời giải
===
---
###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]
---
# [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
## Lời giải
:::spoiler **Ý tưởng**
- Các dữ kiện của bài có thể được quan sát dưới góc độ của bài toán cái túi như sau:
- Khối lượng tối đa mà cái túi chứa được: Số tiền $x$.
- Khối lượng của mỗi đồ vật: Giá trị của mỗi đồng xu.
- Giá trị của mỗi đồ vật: Số lượng đồng xu tăng lên khi ta lấy thêm một đồng xu, tức là $1$.
- Ta có thể lấy số đồ vật tuỳ ý: Ta có thể lấy vô số các đồng xu của mỗi mệnh giá.
- Ta phải làm cho tổng giá trị của các đồ vật trong túi là nhỏ nhất: Ta phải làm cho số đồng xu được chọn để tạo ra số tiền $x$ là ít nhất.
- Từ đó, ta áp dụng quy hoạch động cái túi:
- Gọi `dp[j]` là số đồng xu cần ít nhất để tạo ra số tiền `j`.
- Trường hợp suy biến: `dp[c[i]] = 1` - ta cần đúng `1` đồng xu để tạo ra các số tiền `c[i]` vì ta đã có sẵn các đồng xu giá trị `c[i]`.
- Ta duyệt qua mọi số tiền `j` từ `1` đến `x`, với mỗi số tiền, duyệt qua mọi mệnh giá `c[i]`:
- Nếu `j - c[i] > 0` và `dp[j - c[i]] > 0`, tức là nếu số tiền `j` có thể được tạo ra với đồng xu mệnh giá `c[i]` và số tiền `j - c[i]` cũng có thể được tạo ra (ta không cần xét `j - c[i] = 0` vì nó và`dp[j - c[i]] = 0` không bao giờ đồng thời thoả mão):
- Nếu `dp[j] = 0`, tức là ta chưa tính toán cách tạo ra số tiền `j`: Gán `dp[j] = dp[j - c[i]] + 1`, tức là ta có thể tạo ra số tiền `j` bằng cách thêm `1` đồng xu mệnh giá `c[i]` vào số tiền `j - c[i]`.
- Nếu `dp[j] > 0`, tức là ta đã tính toán ra một cách (sử dụng ít đồng xu nhất tại thời điểm đó) tạo ra số tiền `j`: Gán `dp[j] = min(dp[j], dp[j - c[i]] + 1`, tức là ta thử xem so với cách ta đã có thì cách thêm `1` đồng xu mệnh giá `c[i]` vào số tiền `j - c[i]` có sử dụng ít đồng xu hơn không.
- Sau khi duyệt và tính toán, nếu `dp[j] = 0` thì có nghĩa là không có cách nào để tạo ra số tiền `j`. Vậy, nếu `dp[x] = 0` thì ta in ra `-1`, còn không thì ta in ra `dp[x]`.
:::
:::spoiler **Cài đặt**
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, x, c[1000005], dp[1000005];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> x;
for (int i = 1; i <= n; i++)
{
cin >> c[i];
dp[c[i]] = 1;
}
for (int j = 1; j <= x; j++)
{
for (int i = 1; i <= n; i++)
{
if (j - c[i] > 0 && dp[j - c[i]])
{
if (!dp[j]) dp[j] = dp[j - c[i]] + 1;
else dp[j] = min(dp[j], dp[j - c[i]] + 1);
}
}
}
if (dp[x] == 0) cout << -1;
else cout << dp[x];
return 0;
}
```
:::
# [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`
## Lời giải
:::spoiler **Ý tưởng**
- Các dữ kiện của bài có thể được quan sát dưới góc độ của bài toán cái túi như sau:
- Khối lượng tối đa mà cái túi chứa được: Số tiền $x$.
- Khối lượng của mỗi đồ vật: Giá trị của mỗi đồng xu.
- Giá trị của mỗi đồ vật: Số lượng đồng xu tăng lên khi ta lấy thêm một đồng xu, tức là $1$.
- Ta có thể lấy số đồ vật tuỳ ý: Ta có thể lấy vô số các đồng xu của mỗi mệnh giá.
- Ta phải tính tổng số cách để chứa đầy cái túi: Ta phải tính tổng số cách tạo ra số tiền $x$.
- Từ đó, ta áp dụng quy hoạch động cái túi:
- Gọi `dp[j]` là cách để tạo ra số tiền `j`.
- Trường hợp suy biến: `dp[0] = 1` - ta có `1` cách để tạo ra số tiền `0`, đó là không sử dụng bất kì đồng xu nào cả.
- Ta duyệt qua mọi số tiền `j` từ `1` đến `x`, với mỗi số tiền, duyệt qua mọi mệnh giá `c[i]`:
- Nếu `j - c[i] >= 0`, tức là nếu số tiền `j` có thể được tạo ra với một đồng xu mệnh giá `c[i]`: Ta gán `dp[j] = (dp[j] + dp[j - c[i]]) % MOD` (với `const long long MOD = 1e9 + 7`), tức là ta có thêm `dp[j - c[i]]` cách để tạo ra số tiền `j` vì ta chỉ cần thêm một đồng xu mệnh giá `c[i]` vào mỗi cách đó.
- Sau khi duyệt và tính toán, ta in ra `dp[x]`.
:::
:::spoiler **Cài đặt**
```cpp
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
int n, x, a[1000005];
long long dp[1000005];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> x;
for (int i = 1; i <= n; i++) cin >> a[i];
dp[0] = 1;
for (int i = 1; i <= x; i++)
{
for (int j = 1; j <= n; j++)
{
if (i - a[j] >= 0) dp[i] = (dp[i] + dp[i - a[j]]) % MOD;
}
}
cout << dp[x];
return 0;
}
```
:::
# [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`
## Lời giải
:::spoiler **Ý tưởng**
- Các dữ kiện của bài có thể được quan sát dưới góc độ của bài toán cái túi như sau:
- Khối lượng tối đa mà cái túi chứa được: Số tiền $x$.
- Khối lượng của mỗi đồ vật: Giá trị của mỗi đồng xu.
- Giá trị của mỗi đồ vật: Số lượng đồng xu tăng lên khi ta lấy thêm một đồng xu, tức là $1$.
- Ta có thể lấy số đồ vật tuỳ ý: Ta có thể lấy vô số các đồng xu của mỗi mệnh giá.
- Ta phải tính tổng số cách để chứa đầy cái túi: Ta phải tính tổng số cách tạo ra số tiền $x$.
- **Lưu ý:** Trong bài này, ta phải để vòng lặp duyệt qua các mệnh giá ở ngoài vòng lặp duyệt qua các số tiền. Bằng cách này, một cách tạo ra số tiền bất kì vẫn sẽ có thể có nhiều đồng xu cùng mệnh giá nhưng mỗi mệnh giá sẽ được đưa vào tính toán theo thứ tự mà đề bài cho nên không thể có những cách mới được tạo ra bằng cách thêm những mệnh giá đứng trước vào các cách đã có những mệnh giá đứng sau (từ vòng lặp trước) - nguồn gốc của những cách mới là sự hoán đổi vị trí của những cách cũ. Ví dụ: Nếu đề cho các mệnh giá theo thứ tự là `[3, 2]` thì để tạo ra số tiền `8` ta chỉ có thể có các cách `[2, 2, 2, 2]`, `[3, 3, 2]` chứ không có `[3, 2, 3]` hay `[2, 3, 3]` với cách làm này.
- Từ đó, ta áp dụng quy hoạch động cái túi:
- Gọi `dp[j]` là cách để tạo ra số tiền `j`.
- Trường hợp suy biến: `dp[0] = 1` - ta có `1` cách để tạo ra số tiền `0`, đó là không sử dụng bất kì đồng xu nào cả.
- Ta duyệt qua mọi mệnh giá `c[i]`, với mỗi mệnh giá, duyệt qua số tiền `j` từ `1` đến `x`:
- Nếu `j - c[i] >= 0`, tức là nếu số tiền `j` có thể được tạo ra với đồng xu `c[i]`: Ta gán `dp[j] = (dp[j] + dp[j - c[i]]) % MOD` (với `const long long MOD = 1e9 + 7`), tức là ta có thêm `dp[j - c[i]]` cách để tạo ra số tiền `j` vì ta chỉ cần thêm đồng xu `c[i]` vào mỗi cách đó.
- Sau khi duyệt và tính toán, ta in ra `dp[x]`.
:::
:::spoiler **Cài đặt**
```cpp
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
int n, x, a[1000005];
long long dp[1000005];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> x;
for (int i = 1; i <= n; i++) cin >> a[i];
dp[0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= x; j++)
{
if (j - a[i] >= 0) dp[j] = (dp[j] + dp[j - a[i]]) % MOD;
}
}
cout << dp[x];
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet