Project Euler 31で検索アルゴリズムが動作しないのはなぜですか？

Question

問題31

イングランドで

通貨はポンドで構成され、£、とされペンス、P、および 一般流通で8枚のコインがあります：1P、2P、5P、10P、20P、 50Pは、 £1（100p）と£2（200p）です。 の方法で£2を作ることは可能です：1×1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p どのように多くの数字を使って£2を作ることができますかコインの？

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です。 。

が

Answer 1

の検索アルゴリズムはしない： 私は私のアルゴリズムは、これは私のアルゴリズムがどのように動作するかの可視化がある200

等しい一つ一つの可能​​な組み合わせに達する必要があるので、これはなぜ起こるか分かりません最後のピボットを前のアイテムよりも前に考慮する必要があるときには、最後のピボットを次の低い数字にシフトするだけなので、£2を構成するコインの可能な組み合わせをすべて見つけることができます。

あなたのアルゴリズムは、この組み合わせを見つける：
100、50、20、20、5、2、2、1
ではなく、この：
100、20、20、20、10、5 、2、2、1

2番目の組み合わせの値は50ではありませんが、アルゴリズムはコインの値を後ろに分けて転送するだけです次の "ピボット"がすべて1になるまで50を分解することはありません。カウンターnがインクリメントされるたびにHashMap<Integer,Integer> pivotsを印刷すると、簡単にわかります。

shift()に改訂してコードを修正しようとすると、最後のピボットだけでなく以前のすべてのピボットも使用できます。しかし、そうすることでたくさんの複製が作成されるため、見つかった組み合わせのリストを保持する必要があります。

問題31を解決する別の方法は、動的プログラミングを使用することです。動的プログラミングは、より小さなビットで細分化することができる問題については、最善の方法です。例えば、同じ問題の解決策であるが、 target = 2が問題を解決するために使用できる場合は、target = 10などの問題を解決するために使用できるtarget = 5が解決されます。

幸運を祈る！