import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* c1...cn个硬币,面值各不相同,现要用最少的硬币数,使得钱数为k,给出方案
* @author sky
*
* 设dp[i]为k为i时,最少需要的硬币个数
* dp[0]=1
dp[i] = min(dp[i-cons[j]])+1
*/
public class MinIcons {
private List<Integer> cn;
private Integer k;
public MinIcons(List<Integer> cn, int k){
this.cn = cn;
this.k = k;
}
public int getMinIconNumber(){
Map<Integer,Integer> dp = new HashMap<Integer, Integer>();
dp.put(0, 0);
for(int i=1; i<=k;i++) {
int tmp = i;
for(int j=0;j<cn.size();j++){
if(i >= cn.get(j)) {
tmp = min(tmp,dp.get(i-cn.get(j))+1);
}
}
dp.put(i,tmp);
}
return dp.get(this.k);
}
public int min(int x, int y){
if(x>y) {
return y;
}
return x;
}
public static void main(String[] args) {
List<Integer> l = new ArrayList<Integer>();
l.add(1);
l.add(2);
l.add(5);
System.out.print(new MinIcons(l,103).getMinIconNumber());
}
}
分享到:
相关推荐
对于任意钱数,设计一个用最少硬币找钱的方法 数据输入:由文件input.txt提供输入数据,文件的第一行中只有一个整数给出n的值,第二行起每行2个数,分别是T[j]和cion[j].最后一行是要找的钱数m。 解题思路:可以...
最少零钱问题,最少硬币问题,动态规划算法,找零钱问题,
对于给定的1≤n≤10,硬币面值数组T和可以使用的各种面值的硬币个数数组Coins,以及钱数m,0≤m≤20001,编程计算找钱m的最少硬币数。 数据输入: 第一行中只有1 个整数给出n的值,第2 行起每行2 个数,分别是T[j]和...
设有n 种不同面值的硬币,各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱。...计算出最少硬币数,每个答案一行,问题无解时输出-1。 Sample Input 3 1 3 2 3 5 3 18 Sample Output 5
设计算法求解最少硬币问题,并编程实现,超市找零钱时,找钱数最少的方法
最少硬币问题 动态规划算法 通过ACM网站accept
算法设计-动态规划法解决最少硬币问题源代码
算法分析 关于动态规划的最少硬币问题的代码,
贪心算法——用最少硬币找出n分钱的问题,以及代码。终于解决了
在1次购物中希望使用最少硬币个数。例如,1次购物需要付款0.55元,没有5角的硬币,只好用2*20+10+5共4枚硬币来付款。如果付出1元,找回4角5分,同样需要4枚硬币。但是如果付出1.05元(1枚1元和1枚5分),找回5角,只...
最少硬币问题 动态规划动态规划动态规划动态规划动态规划v
贪心算法求解最少硬币问题C语言程序,问题描述:给顾客找零钱时,收银处有1元,5角和1角硬币若干,如何用最少数量的硬币找够零钱? 算法思想:比如要找给顾客2元9角钱,首先计算1元最多可以有多少枚,即2枚,减去2元,还...
使用各种面值的硬币,现用这些硬币找钱 对任意钱数,用最少钱币找钱的方法
算法的一道题目,最少硬币问题,题目要求是由文件input.txt提供输入数据,文件的第1行中只有1个整数给出 的值,第2行起每行2个数,分别是 和 。最后1行是要找到钱数 。
最少硬币问题.note
这是一个利用动态规划的最少硬币找零算法,时间效率符合要求
对最少硬币兑换问题的算法进行了分析,并给出了实现
用动规实现最少硬币问题 #include #include using namespace std; int n,m; int coins[10],T[10]; int f[20002]; int LeastCoin(int n,int m) { for(int i=0;i;i++) f[i]=i+1; //初始化f数组 f[0]=0; for(int ...