湊硬币是動态規劃的一個經典例子，比如有硬币1,3,5，則組合出11有幾種方案，最少硬币個數的有幾種方案。
網上例子一般都是硬币組合1,3,5，如果不是1開頭的就挂了，比如硬币組合是2,5,8，自己編寫了支援所有硬币組合的代碼。
有兩個例子：
輸出和等于target的最小個數硬币組合
/**
* 輸出和等于target的最小個數硬币組合
* @param coins 硬币有哪幾種，如{1,3,5}
* @param target 硬币和等于多少，如13
*/
private static void calcMinCoins(int [] coins, int target)
輸出和等于target的所有硬币組合
/**
* 輸出和等于target的所有硬币組合
* @param coins 硬币有哪幾種，如{1,3,5}
* @param target 硬币和等于多少，如13
*/
private static void calcAllCoins(int [] coins, int target)
調用函數
public static void main(String[] args) {
calcMinCoins(new int[]{2,5,8}, 50);
calcAllCoins(new int[]{2,5,8}, 50);
}
具體代碼如下：
/**
* 輸出和等于target的最小個數硬币組合
* @param coins 硬币有哪幾種，如{1,3,5}
* @param target 硬币和等于多少，如13
*/
private static void calcMinCoins(int [] coins, int target) {
Map map = new HashMap<>();
for(int i=0;i<=target;i++){
List listi = (List)map.get(i);//所有和等于i的組合
if(listi == null){//若沒有則初始化
listi = new ArrayList();
map.put(i,listi);
}
if(i == 0){//所有和等于0的組合是一個空組合
listi.add(new ArrayList());
}
for(int coin : coins){
if(coin <= i){//如果和等于i，減去coin還大于等于0，則找到和等于tmp
int tmp = i - coin;//和等于tmp
List list = (List)map.get(tmp);//所有和等于tmp的組合
if(list == null){//若沒有則初始化
list = new ArrayList();
map.put(tmp,list);
}
for(int j=0;j<list.size();j++){//周遊所有和等于tmp 加上coin 就等于i了
List subList = (List)list.get(j);
List tmp2 = new ArrayList(subList);
tmp2.add(coin);
//把和等于i的組合加進listi中，前提是不重複，并且個數最小，如果比已存的組合包含元素更少，則把已存組合删了
Collections.sort(tmp2);
boolean same = false;
boolean bigger = false;
boolean isMin = false;
for(int k=0;k<listi.size();k++){
List tmpk = (List)listi.get(k);
if(tmpk.size() > tmp2.size()){
isMin = true;
break;
}else{
if(JSON.toJSONString(tmpk).equals(JSON.toJSONString(tmp2))){
same = true;
break;
}
if(tmpk.size() < tmp2.size()){
bigger = true;
break;
}
}
}
if(isMin){
listi.clear();//如果比已存的組合包含元素更少，則把已存組合删了
listi.add(tmp2);//把和等于i的組合加進listi中
}else{
if(!same&&!bigger){
listi.add(tmp2);//把和等于i的組合加進listi中
}
}
}
}
}
//找到最小組合包含幾個元素
int min = 0;
if(listi.size() > 0){
min = ((List)listi.get(0)).size();
}
System.out.println("所有和等于" + i + "的最小組合包含元素個數" + min+" 這些組合為" + listi);
}
}
這個代碼輸出
所有和等于0的最小組合包含元素個數0 這些組合為[[]]
所有和等于1的最小組合包含元素個數0 這些組合為[]
所有和等于2的最小組合包含元素個數1 這些組合為[[2]]
所有和等于3的最小組合包含元素個數0 這些組合為[]
所有和等于4的最小組合包含元素個數2 這些組合為[[2, 2]]
所有和等于5的最小組合包含元素個數1 這些組合為[[5]]
所有和等于6的最小組合包含元素個數3 這些組合為[[2, 2, 2]]
所有和等于7的最小組合包含元素個數2 這些組合為[[2, 5]]
所有和等于8的最小組合包含元素個數1 這些組合為[[8]]
所有和等于9的最小組合包含元素個數3 這些組合為[[2, 2, 5]]
所有和等于10的最小組合包含元素個數2 這些組合為[[2, 8], [5, 5]]
所有和等于11的最小組合包含元素個數4 這些組合為[[2, 2, 2, 5]]
所有和等于12的最小組合包含元素個數3 這些組合為[[2, 2, 8], [2, 5, 5]]
所有和等于13的最小組合包含元素個數2 這些組合為[[5, 8]]
所有和等于14的最小組合包含元素個數4 這些組合為[[2, 2, 2, 8], [2, 2, 5, 5]]
所有和等于15的最小組合包含元素個數3 這些組合為[[2, 5, 8], [5, 5, 5]]
所有和等于16的最小組合包含元素個數2 這些組合為[[8, 8]]
所有和等于17的最小組合包含元素個數4 這些組合為[[2, 2, 5, 8], [2, 5, 5, 5]]
所有和等于18的最小組合包含元素個數3 這些組合為[[2, 8, 8], [5, 5, 8]]
所有和等于19的最小組合包含元素個數5 這些組合為[[2, 2, 2, 5, 8], [2, 2, 5, 5, 5]]
所有和等于20的最小組合包含元素個數4 這些組合為[[2, 2, 8, 8], [2, 5, 5, 8], [5, 5, 5, 5]]。。。後略
/**
* 輸出和等于target的所有硬币組合
* @param coins 硬币有哪幾種，如{1,3,5}
* @param target 硬币和等于多少，如13
*/
private static void calcAllCoins(int [] coins, int target) {
Map map = new HashMap<>();
for(int i=0;i<=target;i++){
List listi = (List)map.get(i);//所有和等于i的組合
if(listi == null){//若沒有則初始化
listi = new ArrayList();
map.put(i,listi);
}
if(i == 0){//所有和等于0的組合是一個空組合
listi.add(new ArrayList());
}
for(int coin : coins){
if(coin <= i){//如果和等于i，減去coin還大于等于0，則找到和等于tmp
int tmp = i - coin;//和等于tmp
List list = (List)map.get(tmp);//所有和等于tmp的組合
if(list == null){//若沒有則初始化
list = new ArrayList();
map.put(tmp,list);
}
for(int j=0;j<list.size();j++){//周遊所有和等于tmp 加上coin 就等于i了
List subList = (List)list.get(j);
List tmp2 = new ArrayList(subList);
tmp2.add(coin);
//把和等于i的組合加進listi中，前提是不重複
Collections.sort(tmp2);
boolean same = false;
for(int k=0;k<listi.size();k++){
List tmpk = (List)listi.get(k);
if(JSON.toJSONString(tmpk).equals(JSON.toJSONString(tmp2))){
same = true;
break;
}
}
if(!same){
listi.add(tmp2);//把和等于i的組合加進listi中
}
}
}
}
System.out.println("所有和等于" + i + "的組合為" + listi);
}
}
這個代碼輸出
所有和等于0的組合為[[]]
所有和等于1的組合為[]
所有和等于2的組合為[[2]]
所有和等于3的組合為[]
所有和等于4的組合為[[2, 2]]
所有和等于5的組合為[[5]]
所有和等于6的組合為[[2, 2, 2]]
所有和等于7的組合為[[2, 5]]
所有和等于8的組合為[[2, 2, 2, 2], [8]]
所有和等于9的組合為[[2, 2, 5]]
所有和等于10的組合為[[2, 2, 2, 2, 2], [2, 8], [5, 5]]
所有和等于11的組合為[[2, 2, 2, 5]]
所有和等于12的組合為[[2, 2, 2, 2, 2, 2], [2, 2, 8], [2, 5, 5]]
所有和等于13的組合為[[2, 2, 2, 2, 5], [5, 8]]
所有和等于14的組合為[[2, 2, 2, 2, 2, 2, 2], [2, 2, 2, 8], [2, 2, 5, 5]]
所有和等于15的組合為[[2, 2, 2, 2, 2, 5], [2, 5, 8], [5, 5, 5]]
所有和等于16的組合為[[2, 2, 2, 2, 2, 2, 2, 2], [2, 2, 2, 2, 8], [2, 2, 2, 5, 5], [8, 8]]
所有和等于17的組合為[[2, 2, 2, 2, 2, 2, 5], [2, 2, 5, 8], [2, 5, 5, 5]]
所有和等于18的組合為[[2, 2, 2, 2, 2, 2, 2, 2, 2], [2, 2, 2, 2, 2, 8], [2, 2, 2, 2, 5, 5], [2, 8, 8], [5, 5, 8]]
所有和等于19的組合為[[2, 2, 2, 2, 2, 2, 2, 5], [2, 2, 2, 5, 8], [2, 2, 5, 5, 5]]
所有和等于20的組合為[[2, 2, 2, 2, 2, 2, 2, 2, 2, 2], [2, 2, 2, 2, 2, 2, 8], [2, 2, 2, 2, 2, 5, 5], [2, 2, 8, 8], [2, 5, 5, 8], [5, 5, 5, 5]]
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)