3

我的任务是找到一种方法来显示所有可能的方式来回馈预定值的更改，这些值是从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

输出

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

因此，使用 my 中的数字coinTypes ArrayList，我需要一个通用代码算法来显示所有可能的接收方式，例如，使用文件中的硬币返回 143（1.43 美元）零钱，所有便士都是最后一种显示方式。

请不要以为我想让你给我写算法，我只是想帮助写一个，否则我什么也学不会。谢谢大家的任何回答或帮助，您可以给予这对我来说意义重大！如果我遗漏了什么或者您需要更多信息，请告诉我

4

1 回答 1

4

你走过的例子似乎大部分是正确的。唯一的错误是：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!");
}
于 2014-11-23T23:17:17.460 回答