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

Question

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

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 

OU TPUT

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!"); 
}