为什么我的搜索算法不适用于Project Euler 31？

Question

问题31

在英国货币由磅，£和便士，p和 有八个硬币在一般循环：1P，2P，5P，10便士，20P， 50P， 1英镑（100便士）和2英镑（200便士）。可以按以下方式在 中赚取2英镑：1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p使用任意数量可以制作多少种不同的方式硬币？

static int[] nums = {200,100,50,20,10,5,2,1}; 
static int size = nums.length; 
static HashMap<Integer,Integer> pivots = new HashMap<>(); 

public static int checkSum(HashMap<Integer,Integer> pivots){ 

    int target = 200; 
    int sum = 0; 

    for(Integer key: pivots.keySet()){ 
     int pivot = pivots.get(key); 
     sum += nums[pivot]; 
     if(sum > target) return 1; 
    } 

    if(sum < target) return -1; 

    return 0; 
} 

public static void shift(HashMap<Integer,Integer> pivots, int pivot_node){ 

    if(pivots.size() + nums[pivots.get(1)] == 201 && pivots.get(1) != 0){ 

     int p_1_value = pivots.get(1); //this part checks whether the current node(which is the first node)                 
            //has reached children of all 1. 
          //Which means it's time to shift the root node. 
     pivots.clear(); 
     pivots.put(1 , p_1_value); 
     shift(pivots, 1); 
     return; 
    } 

    if(pivots.get(pivot_node) != size - 1) { 
     pivots.put(pivot_node, pivots.get(pivot_node) + 1); 
    } 
    else{ 
     shift(pivots , pivot_node - 1); 
    } 

} 



public static void branch(HashMap<Integer,Integer> pivots){ 
    pivots.put(pivots.size() + 1, pivots.get(pivots.size())); 
} 

public static int search(){ 
    int bool = checkSum(pivots); 

    int n = 0; 
    int count = 0; 

    while(n < 25) { 
     count++; 
     if (bool == 0) { 
      n++;  // if the sum is equal to 200, we shift the last 
        //pivot to the next lower number.    
      shift(pivots, pivots.size()); 

     }else if (bool == -1) { 
      branch(pivots); //if the sum is less than 200, we make a new pivot with value of the last pivot. 
     }else if (bool == 1) {  
      shift(pivots, pivots.size()); //if the sum is greater than 200, 
              //we shift to the last pivot to the next lower number. 
     } 
     bool = checkSum(pivots); 
    } 
    return n; 
} 

public static void main(String[] args){ 

    pivots.put(1,0); 

    int n = search(); 

    System.out.print("\n\n------------\n\n"+ "n: " + n); 

} 

这是一种算法，搜索一组加起来靶的组合。这有点像深度优先搜索树而不使用树。每个支点表示“树”上的节点。 shift（）方法将节点的值更改为下一个更低的值。 branch（）方法使用最后一个节点的相同值创建一个新节点。校验和（）方法检查枢轴的总和是否<，或者=>目标，200

的路数正确的答案应该是围绕73000.但我的算法只返回约300办法。 我不知道为什么会这样，因为我的算法应达到可等于200

这是我的算法是如何工作的一个可视化的每一个可能的组合：

Answer 1

你的搜索算法不找到组成2英镑的所有可能的硬币组合，因为您只是将“最后一个数据点”移动到下一个较低的数字，而您应该在最后一个数字之前考虑这些项目。

你的算法会发现这样的组合：
100，50，20，20，5，2，2，1
但不是这样：
100，20，20，20，10，5 ，2,2,1

第二个组合的值不是50，但是您的算法将硬币值向后分解为仅向前转发-ie它将永远不会分解50，直到所有下面的“支点”均为1.您可以很容易地看到，如果每次计数器n递增时打印您的HashMap<Integer,Integer> pivots。

你可以尝试修改你的代码，修改为shift()不仅使用最后一个枢轴，但也是所有不同的以前的枢轴。但是，这样做会造成很多重复，因此您需要保留不同组合的列表。

解决问题31的另一种方法是使用动态编程。动态规划对于可以以较小比特分解的问题来说是最好的。比如解决同样的问题，但是其中的 target = 2可以用来解决问题，其中target = 5，这可以用来解决问题，其中target = 10等等。

祝你好运！