1

下午好，

我目前正在开发一个程序，该程序应该使用回溯算法来找到达到一定数量所需的硬币总数的解决方案。

程序的基本布局是这样的

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;
    }
}
}

问候，迈克

4

1 回答 1

2

您的基本算法将如下所示：

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.

通过回溯，您通常会保留在算法的每次迭代中分配的剩余数量（因此是“回溯”，因为您正在尝试为越来越小的数量寻找解决方案）。例如，假设我正在寻找 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() + ",");
      }
    }
  }
}
于 2013-03-20T20:34:51.183 回答