Java的回溯与硬币

Question

下午好，

我目前的工作是应该用一个回溯算法找到硬币将需要达到一定的金额总数的解决方案的程序。

该方案的基本布局是这样的

User is prompted for an amount (ie. 123) 
int amount = input.nextInt(); 

User is prompted for number of coins (ie. 6) 
int numCoins = input.nextInt(); 

User is prompted for coin values (ie. 2, 4, 32, 51, 82) 
int[] array = new array[] {2, 4, 32, 51, 82}; 

从这些信息中，我开发一个回溯算法输出解决方案。
我曾尝试查找回溯信息，但无济于事。对我来说，这一切似乎都很不清楚 我正好想到从算法开始。

任何帮助表示赞赏。

编辑

这是目前我一直在努力......这是目前没有工作

public class coins 
{ 

public static int[] coinValues; 
public static int currentAmount = 0; 

public static void main(String[] args) 
{ 
    ArrayList<Integer> temp = new ArrayList<>(); 
    Scanner input = new Scanner(System.in); 

    System.out.println("Please enter the amount: "); 
    int amount = input.nextInt(); 

    System.out.println("Please enter the number of coins: "); 
    int numCoins = input.nextInt(); 
    coinValues = new int[numCoins]; 

    for (int i = 0; i < numCoins; i++) 
    { 
     System.out.println("Please enter coin value of " + i + " :"); 
     int value = input.nextInt(); 
     coinValues[i] = value; 
    } 

    for (int i = 0; i < coinValues.length; i++) 
    { 
     System.out.print("Coin Value: " + i + " " + coinValues[i] + "\n"); 
    } 

    tryThis(temp, amount); 

    for (int i = 0; i < temp.size(); i++) 
    { 
     System.out.println(temp.get(i) + " " + " "); 
    } 
} 

public static ArrayList<Integer> tryThis(ArrayList<Integer> list, int amount) 
{ 
    if (isValid(list, amount) == false) 
    { 
     while (amount > currentAmount && (amount > 0)) 
     { 
      for (int i = 0; i < coinValues.length; i++) 
      { 
       for (int k = coinValues.length - 1; k > 0; k--) 
       { 
        list.add(coinValues[k]); 
        int currentCoin = list.get(i); 


        if (amount > currentAmount) 
        { 
         amount = amount - currentCoin; 
         System.out.println("Amount: " + amount); 
        } 

        tryThis(list, amount); 
       } 
      } 
     } 
    } 


    return new ArrayList<>(); 
} 

public static boolean isValid(ArrayList list, int amount) 
{ 
    boolean keepGoing = true; 
    if (amount > currentAmount) 
    { 
     return keepGoing = false; 
    } 
    else 
    { 
     return keepGoing; 
    } 
} 
} 

的问候， 迈克

Answer 1

您的基本算法是这样的：

For a given amount 
    For each coin type 
    Add the coin to a set 
    If the set exceeds the amount, discard that set. 
    If the set contains more coins than it should, discard the set. 
    If the set equals the amount, add that set to the set of valid possibilities. 
    Otherwise run the algorithm on each set you've created. 

随着回溯你典型的霍尔d到算法的每次迭代所剩下的数量（因此，因为您试图为越来越小的数量寻找解决方案，所以'回溯'）。举例来说，可以说，我正在寻找$ 0.07使用硬币，镍币和便士：

I start with empty sets. 
I add a dime to one set. 
I subtract '10' from my amount. 
This is a negative number, so I discard that set: it is invalid. 
I add a nickel to another (empty) set. 
I subtract '5' from my amount. 
This equals 2; so I'll have to keep working on this set. 
Now I'm working with sets that already include one nickel. 
I add a dime to one set. 
I subtract '10' from my amount. 
This is a negative number, so I discard that set: it is invalid. 
I repeat this with a nickel; I discard this possibility because (2 - 5) is also negative. 
I repeat this with a penny; this is valid but I still have 1 left. 
I repeat this whole process again with a starting set of one nickel and one penny, 
    again discarding a dime and nickel, 
    and finally adding a penny to reach an amount of 0: this is a valid set. 
Now I go back to empty sets and repeat starting with a nickel, then pennies. 

注意，这个算法应该产生多种结果：

[nickel, penny, penny] 
[penny, nickel, penny] 
[penny, penny, nickel] 
[penny, penny, penny, penny, penny, penny, penny] 

函数式语言是这种自然拟合递归工作，但你可以用任何语言复制这个算法。

这将是实现代码的一个例子，不包括重复的优雅修剪：

import java.util.*; 

public class Backtrack { 

    private static List<List<Integer>> findSets(int amount, List<Integer> coinTypes, int numberOfCoins) { 
    List<List<Integer>> results = new ArrayList<List<Integer>>(); 

    for (Integer coin : coinTypes) { 
     List<Integer> result = new ArrayList<Integer>(); 
     result.add(coin); 
     int currentAmount = amount - coin; 
     if (currentAmount >=0) { //only continue if we haven't overshot 
     if (currentAmount == 0) { 
      results.add(result);//this is a valid solution, add it to result set 
     } else {//still some value to make up 
      if ((numberOfCoins - 1) > 0){//otherwise we shouldn't recurse 
      List<List<Integer>> recurseResults = findSets(currentAmount, coinTypes, (numberOfCoins - 1)); 
      for (List<Integer> recurseResult : recurseResults) {//Have to add this layer's coin in to each result 
       recurseResult.add(coin); 
      } 
      results.addAll(recurseResults); 
      } 
     } 
     } 
    } 

    return results; 
    } 

    public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    int amount = 7; 
    List<Integer> coinTypes = new ArrayList<Integer>(); 
    coinTypes.add(Integer.valueOf(1)); 
    coinTypes.add(Integer.valueOf(5)); 
    coinTypes.add(Integer.valueOf(10)); 
    int numberOfCoins = 3; 

    List<List<Integer>> results = findSets(amount, coinTypes, numberOfCoins); 
    System.out.println("Number of results: " + results.size()); 
    for (List<Integer> result : results) { 
     System.out.print("Result: "); 
     for (Integer coin: result) { 
     System.out.println(result.toString() + ","); 
     } 
    } 
    } 
}