带硬币的Java BackTracking

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.

对于回溯，您通常会在算法的每次迭代中保留要分配的剩余数量(因此称为“回溯”，因为您试图找到一个越来越小的数量的解决方案)。例如，假设我正在寻找使用10美分、5美分和1美分的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() + ",");
      }
    }
  }
}