欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最少硬币数问题 博客分类: 数据结构&算法 动态规划最少硬币问题 

程序员文章站 2024-02-24 21:03:46
...
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());
	}
}