Правильный алгоритм рекурсивного возврата?

Question

Мое задание - найти способ отобразить все возможные способы возврата изменений для предварительно определенного значения, значения которого сканируются из txt файл. Это должно быть выполнено с помощью Recursive Backtracking, в противном случае мое решение не будет засчитано. Я буду честен, говоря, что я полностью потерян на том, как кодировать в соответствующем алгоритме. Все, что я знаю, это то, что алгоритм работает примерно так:

 start with empty sets.
 add a dime to one set. 
 subtract '10' from my amount.
 This is a negative number, so I discard that set: it is invalid.
 add a nickel to another (empty) set.
 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.
add a dime to one set.
subtract '10' from my amount.
This is a negative number, so I discard that set: it is invalid.
repeat this with a nickel; I discard this possibility because (2 - 5) is also negative.
repeat this with a penny; this is valid but I still have 1 left.
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.

Проблема в том, что я не имею ни малейшего понятия о том, как или с чего начать, только о том, что должно быть достигнуто, или если какие-либо другие решения очевидны.

Это мой код до сих пор:

ОБНОВЛЕНО

import java.io.*;
import java.util.*;
import java.lang.*;

public class homework5 {

 public static int penny = 1;
 public static int nickle = 5;
 public static int dime = 10;
 public static int quarter = 25;
 public static int halfDollar = 50;
 public static int dollar = 100;
 public static int change;

  public static void main(String[] args) throws FileNotFoundException {

    ArrayList<Integer> coinTypes = new ArrayList<Integer>();

    Integer i;
    File f = new File (args[0]);
    Scanner input = new Scanner(f);
       input.nextLine();
       while(input.hasNextInt()) {
               i = input.nextInt();
               coinTypes.add(i);
       }
       change = coinTypes.get(coinTypes.size()-1);
       coinTypes.remove(coinTypes.size()-1);
                System.out.println("Found change"); //used for debugging
                System.out.println("Change: " + change);


    System.out.println(coinTypes);
  }
     boolean findChange(int change, List<Integer> coinTypes,
                     List<Integer> answerCoins) {
        if(change == 0) {
          return true;
        }
        if(change < 0) {
          return false;
        } else {
          for(Integer coin : coinTypes) {
              if(findChange(change - coin, coinTypes, answerCoins)){
                 answerCoins.add(coin);
                 return true;
              }
          }

  List<Integer> answer = new ArrayList<Integer>();
   boolean canFindChange = findChange(change, coinTypes, answer);
    if(canFindChange) {
        System.out.println(answer);
    } else { System.out.println("No change found");
      }
   return false;
  }
}

Вот входной файл, который я сканирую

java homework5 hwk5sample1.txt

// Coins available in the USA, given in cents.  Change for $1.43?
1 5 10 25 50 100
143

ВЫХОД

Found change
Change: 143
[1, 5, 10, 25, 50, 100]

Так что используя цифры в моем coinTypesArrayListМне нужен алгоритм общего кода, чтобы показать все возможные способы получения, например, 143 ($1,43) обратно в обмен, используя монеты в файле, причем все копейки были последним способом показать это.

Пожалуйста, не думайте, что я хочу, чтобы вы написали мне алгоритм, я просто хочу помочь написать его, иначе я ничему не научусь. Спасибо всем за любые ответы или помощь, которую вы можете дать, это очень много значит для меня! Пожалуйста, дайте мне знать, если я что-то пропустил или вам нужна дополнительная информация

Answer 1

Пример, через который вы проходите, кажется верным. Единственная ошибка заключается в следующем: again discarding a dime and nickel, который должен быть again discarding a *penny* and nickel (но я думаю, что это просто опечатка.)

Чтобы написать рекурсивный алгоритм обратного отслеживания, полезно думать о рекурсивном вызове как о решении подзадачи исходной задачи. В одной возможной реализации решения псевдокод выглядит следующим образом:

/**
 * findChange returns true if it is possible to make *change* cents of change
 *     using the coins in coinTypes. It adds the solution to answerCoins.
 *     If it's impossible to make this amount of change, then it returns false.
 */
boolean findChange(int change, List<Integer> coinTypes, List<Integer> answerCoins) {
    if change is exactly 0: then we're done making change for 0 cents! return true
    if change is negative: we cannot make change for negative cents; return false
    otherwise, for each coin in coinTypes {
        // we solve the subproblem of finding change for (change - coin) cents
        // using the recursive call.
        if we can findChange(change - coin, coinTypes, answerCoins) {
            // then we have a solution to the subproblem of
            // making (change - coins) cents of change, so:
            - we add coin to answerCoins, the list of coins that we have used
            - we return true // because this is a solution for the original problem
        }
    }
    //if we get to the next line, then we can't find change for any of our subproblems
    return false
}

Мы бы назвали этот метод с:

List<Integer> answer = new ArrayList<Integer>();
boolean canFindChange = findChange(change, coinTypes, answer);
if(canFindChange) {
    System.out.println(answer); // your desired output.
}
else {
    System.out.println("Can't find change!");
}