算法:硬币凑整问题【拓展:输出凑整方案】
程序员文章站
2022-03-16 14:57:03
题目:给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。你可以认为每种硬币的数量是无限的。示例 1输入:coins = [1, 2, 5], amount = 11输出:3解释:11 = 5 + 5 + 1示例 2:输入:coins = [2], amount = 3输出:-1示例 3:输入:coins = [1], amount = 0......
最近碰到一个算法题,有哪位算法大神可以指点一下。
去网上也搜索了很多,如果只需要获得硬币个数,那么直接搜索关键词:动态规划,有很多答案。
但是我碰到的实际生产过程,很多需要输出具体执行方案,所以研究了一下怎么写代码。
【只做题的可以跳过了】
题目:
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1
输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1
示例 2:
输入:coins = [2], amount = 3
输出:-1
示例 3:
输入:coins = [1], amount = 0
输出:0
示例 4:
输入:coins = [1], amount = 1
输出:1
示例 5:
输入:coins = [1], amount = 2
输出:2
提示:
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
解题思路:
贪心算法是局部最优解,那么从不同切入点进行贪心,总是能够获取到最优解,再从最优解中攫取真正的最优解。
既可以利用贪心算法的速度,又能够兼顾获取最终最优解。
我的代码,呼叫大家一起研究一下
package com.example.demo.algorithm;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* 多次贪心,获取最优解
*/
public class Exhausting {
// 遍历结果集
private static final Set<List<Integer>> results = new HashSet<>();
// 面额
private static final int[] coinsArray = {6, 5, 2, 1};
// 总金额
private static final int amount = 15;
// 每次循环的次数
private static int count = 0;
// 总循环次数
private static int count2 = 0;
public static void main(String[] args) {
// 按不同切入点,多次贪心
for (int i = 0; i < coinsArray.length; i++) {
// 执行贪心
execute(i, 0, new ArrayList<Integer>());
// 每次贪心后,重置次循环count
count = 0;
System.out.println("-------------------------分隔符----------------------------");
}
System.out.println("遍历结果集为:");
printResult(results);
Set<List<Integer>> bestResults = getBestResults();
System.out.println("最优解为:");
printResult(bestResults);
}
/**
* 递归函数:贪心算法
* a 层级参数
* tempCountAmount 当前累加结果
* tempResult 当前累加结果
**/
private static void execute(int rank, Integer tempCountAmount, List<Integer> tempResult) {
tempCountAmount += coinsArray[rank];
if (tempCountAmount > amount) {
System.out.println("========1==========count:" + (++count) + ",count2:" + (++count2));
// 判断是否是最后一层
if (rank == coinsArray.length - 1) {
// 是最后一层不符合
return;
}
// 抛弃上层结果,使用下层面额继续累加
tempCountAmount -= coinsArray[rank];
execute(rank + 1, tempCountAmount, tempResult);
} else if (tempCountAmount == amount) {
System.out.println("========2==========count:" + (++count) + ",count2:" + (++count2));
// 保留的结果
tempResult.add(coinsArray[rank]);
results.add(tempResult);
} else {
System.out.println("========3==========count:" + (++count) + ",count2:" + (++count2));
// 记录当前结果
tempResult.add(coinsArray[rank]);
// 当前层级继续累加
execute(rank, tempCountAmount, tempResult);
}
}
/**
* 获取最优解
* @return 最优解集
*/
private static Set<List<Integer>> getBestResults() {
// 最优解
Set<List<Integer>> bestResults = new HashSet<>();
int resultCoins = Integer.MAX_VALUE;
// 为了方便展示所有贪心结果,在最后去处理结果
for (List<Integer> result : results) {
if(result.size() < resultCoins){
bestResults.clear();
bestResults.add(result);
resultCoins = result.size();
}else if(result.size() == resultCoins){
bestResults.add(result);
}
}
return bestResults;
}
/**
* 打印解
* @param results 解集
*/
private static void printResult(Set<List<Integer>> results) {
for (List<Integer> result : results) {
StringBuilder resultStr = new StringBuilder("result:");
for (Integer integer : result) {
resultStr.append(integer).append(",");
}
System.out.println("size:["+result.size()+"],"+resultStr.substring(0, resultStr.length() - 1).toString());
}
}
}
数输出结果大概是这样的:
本文地址:https://blog.csdn.net/qq_35757473/article/details/109942254