写一段java代码,题目如下:设有6 种不同面值的硬币,各硬币的面值分别为5 分,1 角,2 角,5 角,1 元,2元。现要用这些面值的硬币来购物。在购物中希望使用最少个数硬币。例如,1 次购物需要付款0.55 元,如果没有5 角的硬币,只好用22角+11角+1*5分 共4 枚硬币来付款。 对于给定的各种面值的硬币个数和付款金额,计算使用硬币个数最少的交易方案。 输入格式: 输入数据有若干组,第一行给出一个整数n表示输入数据的组数。 以下n行每一行有6 个整数和1个有2 位小数的实数。分别表示可以使用的各种面值的硬币个数和付款金额。 输出格式: 输出每组数据的最少硬币个数。如果不可能完成交易,则输出“impossible”。
时间: 2024-02-01 17:15:20 浏览: 28
以下是Java代码实现:
```java
import java.util.Scanner;
public class Main {
static int[] coins = {200, 100, 50, 20, 10, 5}; // 硬币面值(单位为分)
static int[] count = new int[6]; // 硬币数量
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 组数
while (n-- > 0) {
for (int i = 0; i < 6; i++) {
count[i] = sc.nextInt();
}
double money = sc.nextDouble(); // 付款金额(单位为元)
int target = (int) (money * 100); // 付款金额(单位为分)
int[] dp = new int[target + 1]; // dp[i]表示付款金额为i分时使用的最少硬币个数
for (int i = 1; i <= target; i++) {
dp[i] = Integer.MAX_VALUE; // 初始化为最大值
for (int j = 0; j < 6; j++) {
if (i >= coins[j] && count[j] > 0) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1); // 转移方程
}
}
}
if (dp[target] == Integer.MAX_VALUE) {
System.out.println("impossible");
} else {
System.out.println(dp[target]);
}
}
}
}
```
算法思路:
使用动态规划算法,设dp[i]表示付款金额为i分时使用的最少硬币个数。则有转移方程:
$$dp[i] = \min(dp[i], dp[i - coins[j]] + 1)$$
其中coins[j]表示第j种面值的硬币,dp[i-coins[j]]表示付款金额为i-coins[j]分时使用的最少硬币个数。因此,只需要遍历每种面值的硬币,如果当前面值的硬币可以使用(即i大于等于当前面值的硬币,且当前面值的硬币数量大于0),则更新dp[i]的值。
最后判断dp[target]的值是否为Integer.MAX_VALUE,如果是,则输出"impossible";否则,输出dp[target]的值即可。
相关推荐
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)