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

Question

问题 31

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation: 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). It is possible to make £2 in the following way: 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p How many different ways can £2 be made using any number of coins?

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() 方法创建一个与上一个节点具有相同值的新节点。 checkSum() 方法检查枢轴的总和是否为 <,= 或 > 目标 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，但是您的算法将硬币值从后向分解为仅向前 - 即在以下所有“枢轴”均为 1 之前，它永远不会分解为 50。如果您打印 HashMap<Integer,Integer> pivots，您可以很容易地看到这一点。每次计数器 n 递增。

您可以尝试通过将代码修改为 shift() 来修复您的代码不仅使用最后一个枢轴，还使用所有不同的先前枢轴。但是，这样做会创建很多重复项，因此您需要保留一份已找到的不同组合的列表。

解决问题 31 的另一种方法是使用动态规划。当涉及到可以分解成更小部分的问题时，动态规划是最好的。例如，同一问题的解决方案，但在哪里 target = 2可用于解决问题所在 target = 5 ，可用于解决 target = 10 的问题等等。

祝你好运!