2016-03-04 51 views
0

我試圖打印給定數量的所有路徑。但我的代碼無法正常工作。我想我錯過了一些要打印所有可能的組合。例如;遞歸硬幣更改通過打印所有可能的方式進行製作

  • 如果量:7和startCoin = 25,程序需要給我: {5,1,1}和{1,1,1,1,1,1,1}。

你能幫我解決這些問題嗎?

注:最好的Java解決方案

class Solution { 

     static int[] coinSet = {1,5,10,25}; 
     static List<List<Integer>> possibleWays = new ArrayList<>(); 
     static List<Integer> currentWay = new ArrayList<>(); 

     private static int makeChange(int amount, int startCoin){ 

     boolean flag = false; 
     for(int i =0 ; i < coinSet.length ; i++){ 
      if(coinSet[i] == startCoin) { 
      flag =true; 
      } 
     } 

     if(!flag){ 
      throw new IllegalArgumentException("startCoin has to be in the specified range"); 
     } 

     int nextCoin = 0; 
     switch(startCoin) { 
      case 25: 
      nextCoin = 10; 
      break; 

      case 10: 
      nextCoin = 5; 
      break; 

      case 5: 
      nextCoin = 1; 
      break; 

      case 1: 
      possibleWays.add(currentWay); 
      currentWay = new ArrayList<>(); 
      return 1; 
     } 

     int ways = 0; 

     for(int count = 0; count * startCoin <= amount; count++){ 
      ways += makeChange(amount - (count * startCoin),nextCoin); 
     } 

     return ways; 

     }  
     public int calculateNumberOfWays(int amount, int startCoin) throws Exception { 
     if (amount == 0) { 
      throw new Exception(); } 

     return makeChange(amount, startCoin); 
     } 

     public static void main(String[] args) { 

     System.out.println(makeChange(5,25)); 
     System.out.println(possibleWays); 

     } 
    } 
+0

嗨,你可以看看這裏尋求幫助:http://info.mcip.ro/?cap=Backtracking&prob=368。這不是Java,但它解決了你的問題:)。 如果你仍然困惑,研究一下回溯問題。 –

+0

您是否清楚該解決方案的時間複雜度和空間複雜度?我想這是O(n!),但我不確定。 –

+0

關於複雜性:您可以通過* dynamic programming *避免指數運行時間。當你擁有像5這樣的值的所有解決方案時,像6這樣的值的解決方案就是(所有解1)x(所有解的5)。 – Marco13

回答

0

這可以通過回溯來解決,但不是非常有效的,下面是可以使用的Java代碼

/** 
* Created by sumit sharma on 3/1/2016. 
*/ 
import java.util.ArrayList; 
import java.util.Date; 
import java.util.List; 
import java.util.Random; 

public class Main { 
    static int[] coinSet = {1,5,10,25}; 
    static List<List<Integer>> possibleWays = new ArrayList<>(); 
    static List<Integer> currentWay = new ArrayList<>(); 
    public static void main(String[] args) { 
     List<Integer> countOfCoins = new ArrayList<>(); 
     makeChange(7, 0, countOfCoins); 
     //System.out.print(possibleWays); 
    } 

    private static int makeChange(int amount, int startCoinIdx, List<Integer> coinsSoFar) { 
     if(startCoinIdx == coinSet.length){ 
      if(amount == 0){ 
       possibleWays.add(coinsSoFar); 
       System.out.println(coinsSoFar); 
      } 
      //System.out.println(coinsSoFar); 
      return 0; 
     } 
     for(int count = 0;(count*coinSet[startCoinIdx]) <= amount;count++){ 
      List<Integer> temp = new ArrayList<>(); 
      for(int i = 0;i < coinsSoFar.size();i++) temp.add(coinsSoFar.get(i)); 
      for(int i = 0;i < count;i++) temp.add(coinSet[startCoinIdx]); 
      makeChange(amount - (count * coinSet[startCoinIdx]),startCoinIdx+1, temp); 
      temp.clear(); 
     } 
     return 0; 
    } 
} 

鏈接到解決方案上Ideone:http://ideone.com/kIckmG

+0

正如@ marco13所建議的,動態編程解決方案也可能更加高效,但會增加所需的內存量或空間複雜度。還要注意DP解決方案不是多項式,而是我們所說的僞多項式,因爲它取決於特定輸入所需的內存量。 – uSeemSurprised