我们知道人民币有1、2、5、10、20、50、100这几种面值。 现在给你 n(1≤n≤250)元,让你计算换成用上面这些面额表示且总数不超过100张,共有几种。 比如4元,能用4张1元、2张1元和1张2元、2张 2元,三种表示方法。
时间: 2023-08-31 18:06:02 浏览: 53
这是一个经典的完全背包问题,可以使用动态规划来解决。
定义状态dp[i][j]为使用前i种面值,凑出j元钱的方案数。则状态转移方程为:
dp[i][j] = dp[i-1][j] + dp[i][j-value[i]],其中value[i]表示第i种面值。
初始状态为dp[0][0] = 1,其余为0。最终答案为dp[7][n],因为有7种面值。
以下是Python的实现代码:
```
n = int(input())
value = [0, 1, 2, 5, 10, 20, 50, 100]
dp = [[0 for _ in range(n+1)] for _ in range(8)]
dp[0][0] = 1
for i in range(1, 8):
for j in range(n+1):
dp[i][j] = dp[i-1][j]
if j >= value[i]:
dp[i][j] += dp[i][j-value[i]]
print(dp[7][n])
```
注意题目中要求总数不超过100张,因此在状态转移时需要限制使用第i种面值的张数不超过100张。
相关问题
我们知道人民币有 $1$、$2$、$5$、$10$、$20$、$50$、$100$ 这几种面值。 现在给你 $n$ $(1 \le n \le 250)$ 元,让你计算换成用上面这些面额表示且总数不超过 $100$ 张,共有几种。 比如 $4$ 元,能用 $4$ 张 $1$ 元、$2$ 张 $1$ 元和 $1$ 张 $2$ 元、$2$ 张 $2$ 元三种表示方法。c++
可以使用动态规划来解决这个问题。令 $dp[i][j]$ 表示用前 $i$ 种面额表示 $j$ 元的方案数,则有以下状态转移方程:
$$dp[i][j]=\sum_{k=0}^{\lfloor \frac{j}{v_i} \rfloor}dp[i-1][j-kv_i]$$
其中 $v_i$ 表示第 $i$ 种面额的面值。初始状态为 $dp[0][0]=1$,其余为 $0$。最终答案为 $\sum_{i=0}^{100}dp[7][i]$。
以下是 C++ 代码实现:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
int dp[8][101];
int main() {
int v[8] = {0, 1, 2, 5, 10, 20, 50, 100}; // 面值数组
dp[0][0] = 1;
for (int i = 1; i <= 7; ++i) {
for (int j = 0; j <= 100; ++j) {
for (int k = 0; k <= j / v[i]; ++k) {
dp[i][j] += dp[i - 1][j - k * v[i]];
}
}
}
int n;
while (cin >> n) {
cout << dp[7][n] << endl;
}
return 0;
}
```
注意:本题的输出结果需要每组数据输出一个换行符。\n
取1元、2元和5元纸币共10张,凑整18元,共有几种方法?(用n表示)
这是一个典型的硬币找零问题,可以使用动态规划解决。我们可以定义一个长度为 19 的一维数组 dp,其中 dp[i] 表示凑整 i 元钱的方法数。初始时,dp[0]=1(不选取任何纸币也是一种方法),然后遍历纸币的面额,对于每一种面额的纸币,我们更新数组 dp 中的每个大于等于该面额的元素的值。
根据这个思路,可以得到以下代码:
```python
dp = [0] * 19
dp[0] = 1
for coin in [1, 2, 5]:
for i in range(coin, 19):
dp[i] += dp[i - coin]
n = dp[18]
print(n)
```
因此,凑整18元的方法数为 85 种。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)