用java写出考虑著名找零问题的一般情形:需找零金额为n,最少要用多少面值为d1<d2<…<dm的硬币?
时间: 2023-09-30 13:06:03 浏览: 55
以下是用Java实现找零问题的代码:
```java
public static int minCoins(int[] coins, int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i && dp[i - coins[j]] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[n];
}
```
其中,`coins`是硬币面值的数组,`n`是需找零的金额。我们使用一个一维数组`dp`来记录每个金额需要的最小硬币数。对于每个金额`i`,我们遍历硬币面值数组`coins`,如果当前硬币面值`coins[j]`小于等于`i`,并且`i-coins[j]`的最小硬币数不为无穷大,则更新`dp[i]`为`dp[i-coins[j]]+1`,即当前硬币面值`coins[j]`需要的硬币数加上`i-coins[j]`需要的最小硬币数。最后返回`dp[n]`即可。
相关问题
【问题描述】 考虑著名找零问题的一般情形:需找零金额为n,最少要用多少面值为d1<d
在一般情况下,考虑著名找零问题的需找零金额为n,并且假设面值的最小单位为d1,其中d1<d。要求最少使用多少面值来找零。
首先,我们可以把问题转化为子问题,即找零金额为n时最少需要用到多少面值的硬币。我们可以通过分析问题的子结构和递归的方式来解决。
假设我们有k种面值的硬币,分别为c1, c2, ..., ck,其中ci表示第i种硬币的面值。我们可以将问题分为两种情况来考虑:
1. 当n小于d1时,我们无法使用面值为d1的硬币进行找零,因此必须使用更小面值的硬币。在这种情况下,我们需要找零金额为n时最少需要用到多少面值的硬币等于找零金额为n时最少需要用到多少面值的硬币。
2. 当n大于等于d1时,我们可以选择是否使用面值为d1的硬币。假设我们选择使用面值为d1的硬币,则在找零金额为n时最少需要用到多少面值的硬币等于找零金额为n-d1时最少需要用到多少面值的硬币加上1(即使用了一枚面值为d1的硬币)。
综上所述,我们可以得出以下递归公式来求解最少需要用到多少面值的硬币:
minCoins(n) = min(minCoins(n-d1) + 1, minCoins(n))
其中,minCoins(n-d1) + 1表示使用了一枚面值为d1的硬币,minCoins(n)表示没有使用面值为d1的硬币。
通过使用递归的方式,我们可以依次求解问题的规模,直到求解出只需要用到面值为d1的硬币为止。这样,我们就可以得到最终的答案。
需要注意的是,为了避免重复计算,我们可以使用记忆化的方式来优化递归过程,将已经计算过的结果保存起来。
总结起来,考虑著名找零问题的一般情形,需要找零金额为n时,最少需要用到的面值为d1<d的硬币的数量,可以通过递归求解的方式得到。
用c++完成考虑著名找零问题的一般情形:需找零金额为n,最少要用多少面值为d1<d2<…<dm的硬币?
这个问题可以使用动态规划来解决。我们可以定义一个一维数组 `dp`,其中 `dp[i]` 表示找零金额为 `i` 时所需要的最少硬币数。
初始状态为 `dp[0] = 0`,即找零金额为 0 时不需要硬币。
对于每个 `i`,我们可以枚举所有硬币面值 `di`,这里需要保证 `di <= i`,并更新状态转移方程:
```
dp[i] = min(dp[i], dp[i - di] + 1)
```
其中 `dp[i - di]` 表示找零金额为 `i - di` 时所需要的最少硬币数,加上 1 表示使用一枚面值为 `di` 的硬币。
最终答案为 `dp[n]`。
下面是 C++ 实现代码:
```cpp
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> dp(n + 1, numeric_limits<int>::max());
dp[0] = 0;
vector<int> coins(m);
for (int i = 0; i < m; i++) {
cin >> coins[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m && coins[j] <= i; j++) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
cout << dp[n] << endl;
return 0;
}
```
其中,`n` 表示需找零金额,`m` 表示硬币面值种类数,`coins` 存储硬币面值。
注意,这里使用了 `numeric_limits<int>::max()` 来初始化数组,表示初始状态为无穷大。