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 に答える