根據與目標數相加的組合數計算整數串列的分數-有解無憂

嘗試撰寫一種從數字串列中計算的方法，6這些數字的總和與該數字相加target，其余不能產生目標的數字不應考慮在內。每個號碼最多只能使用一次。

例如：

如果target是12并且一個數字串列是，[6, 6, 6, 6, 6, 6]那么回傳值應該是36。
如果我們收到一個數字串列，[1, 3, 4, 5, 6, 6]并且 atarget應該是12（5 1 6=12而且5 4 3=12，但是，數字只能使用一次并且不能重復使用，因此只有一個組合可以貢獻結果）。

我的代碼在線

編輯：關于這個{6, 6, 6, 6, 6, 6}例子，6 6 = 12，然后如果重復，我們也總結一下。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class MyClass {
    public static void main(String args[]) {
      ArrayList<Integer> numbers = new ArrayList<>(6);
      numbers.add(1);
      numbers.add(3);
      numbers.add(4);
      numbers.add(5);
      numbers.add(6);
      numbers.add(6);
      
      System.out.println(sumRecursively(numbers, 0, 12, new ArrayList<Integer>()));
    }
    
    private static int sumRecursively(ArrayList<Integer> numbers, int sum, int target, ArrayList<Integer> partial) {
        for(int i: partial) sum  = i;
        
        if(sum == target) { return sum; }
        else {
            for(int n = 0; n < numbers.size();   n) {
                partial.add(numbers.remove(n));
                sumRecursively(numbers, sum, target, partial);
            }
        }
        
        return sum;
    }
}

描述：數字可以從1-6, 為陣列串列中的每個單元格/索引生成任何內容six slots in space。數字可以是到之間1的任何值6。但是，主要關注的是盡可能sum達到目標。當兩個或三個 or n-pairs 已用于對匹配目標求和時，則將它們全部洗掉。看看remainders如果有的話，看看他們是否總和目標，return否則sum。

此外，目標范圍是：3-12，3并由LOW表示。所有帶有 LOW 的東西，都被總結為 match 3。

我目前的解決方案不起作用。

我現在寫了這個函式：

private static int sumRecursively(ArrayList<Integer> numbers, 
        int sum, int target, int n) {
    if(sum > target)
        sum = 0;
    if(sum == target) { return sum; }
    sum  = numbers.remove(n);
    return sumRecursively(numbers, sum, target, n);
}

此方法適用于[1, 3, 4, 5, 6, 6]并給出12，因為將前6 的所有內容相加得到 13。但是，如果都是[6,6,6,6,6,6]示例，則總和變為12。因為，它不會繼續下去。

注意：如果您玩過 Yahtzee 游戲，那么您就知道了。

https://en.wikipedia.org/wiki/Yahtzee

新版本：

private static int sumRecursively(ArrayList<Integer> numbers, 
        int sum, int target, int n, ArrayList<Integer> sums) {
        
        if(sum > target)
            sum = 0;
        
        if(numbers.size() == 0) {
            sums.add(sum);
            return sums.stream().mapToInt(Integer::intValue).sum();
        }
        
        if(sum == target) { sums.add(sum); sum = 0; }
        sum  = numbers.remove(n);;
        return sumRecursively(numbers, sum, target, n, sums);
    }

類似的問題仍然存在，例如，對目標12[1,3,2,2,6,5]給出 6 。例如，這里，或。1 5 6 = 123 2 2 5 = 12

問題：整個問題是關于，找出從 1 到 6 的總共 6 個不同數字的串列中的數字組合，總和為目標值。如果潛在的候選者湊齊，這些候選者不能再次被重復使用。檢查余數是否有可能與目標值相加，如果沒有找到，則回傳包含所有目標值的總和串列的總和。例如，得到一個 6 x 6 的串列，目標 6 6=12, 6 6=12 6 6=12 = 那么 36 應該是總和。

這段代碼給出：

static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) 
    {
       int s = 0;
       for (int x: partial) s  = x;
       if (s == target) {
            System.out.println("sum(" Arrays.toString(partial.toArray()) ")=" target);
       }
       if (s >= target)
            return;
       for(int i=0;i<numbers.size();i  ) {
             ArrayList<Integer> remaining = new ArrayList<Integer>();
             int n = numbers.get(i);
             for (int j=i 1; j<numbers.size();j  ) remaining.add(numbers.get(j));
             ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
             partial_rec.add(n);
             sum_up_recursive(remaining,target,partial_rec);
       }
    }
    
    static void sum_up(ArrayList<Integer> numbers, int target) {
        sum_up_recursive(numbers,target,new ArrayList<Integer>());
    }

用法：

Integer[] numbers = {1,3,4,5,6,6};
        sum_up(new ArrayList<Integer>(Arrays.asList(numbers)), 12);

輸出：

sum([1, 5, 6])=12
sum([1, 5, 6])=12
sum([3, 4, 5])=12
sum([6, 6])=12

問題：如何停止，一旦找到一個組合，并確保重復使用不同的數字。

uj5u.com熱心網友回復：

為了確保每個組合中的所有元素都是唯一的，我們會跟蹤已使用的索引。即每次我們找到一個總和等于目標數的組合時，我們應該禁止使用已在該組合中使用過的元素，但不能更早（因為可能有很多組合無法產生目標，并且因此，任何元素都應該有資格被使用，直到我們沒有構建一個完整的組合來給目標使用這個元素）。

為了跟蹤所采用的元素，我們需要一個在每個遞回分支中都可見的物件。并且我們已經在每次遞回呼叫時傳遞了一個數字串列，如果我們每次找到一個通過洗掉該組合中已使用的元素來生成目標數字的組合時都修改它會怎樣？如果我們在第一次組合之后走這條路，事情會變得復雜，因為我們將無法依賴索引（因為它們可以以不可預測的方式改變) 在構建單個組合時 - 確保屬于特定組合的每個元素在組合中僅使用一次至關重要。由于元素的值可能相同，我們應該使用迭代順序來正確構造每個組合，但是每次洗掉元素都會造成混亂。那么，有沒有更好的方法呢？

我們可以維護一個boolean值陣列，每個元素是這個陣列將指示特定索引處的數字是否已經屬于給定目標的組合。

我沒有將遞回方法與操作該boolean陣列的代碼混為一談，而是使用簡單且不言自明的方法將其封裝在一個類中，并sumRecursively()使用了該類的一個實體。

public class CombinationTracker {
    private boolean[] isUsed;
    
    public CombinationTracker(int size) {
        this.isUsed = new boolean[size];
    }
    
    public boolean indexIsUsed(int ind) {
        return isUsed[ind];
    }
    
    public boolean allNotUsed(List<Integer> indices) {
//            return indices.stream().noneMatch(i -> isUsed[i]); // this line does the same as the loop below
        
        boolean result = true;
        for (int idx: indices) {
            if (isUsed[idx]) {
                result = false;
                break;
            }
        }
        return result;
    }
    
    public void setIsUsed(List<Integer> indices) {
        for (int ind: indices)
            setIsUsed(ind);
    }
    
    public void setIsUsed(int ind) {
        isUsed[ind] = true;
    }
}

使用這種方法，我們能夠從尚未使用的數字構造組合，并通過在進行遞回呼叫時傳遞索引來迭代從特定位置開始的數字串列。我們可以確定，任何位于當前位置之前的元素都不會添加到當前組合中。

現在，快速回顧一下遞回。

每個遞回實作都由兩部分組成：

基本情況- 表示預先知道結果的邊緣情況（或一組邊緣情況）。對于這個問題，有兩種極端情況：
- 我們已經設法找到一個給出目標數的組合，即currentSum == target，結果將等于target;
- 到達串列的末尾（并且組合不會導致目標），結果將是（這種邊緣情況通過遞回情況下回圈0的終止條件自動解決，因此無需單獨處理）。for
遞回案例- 進行遞回呼叫和主要邏輯所在的解決方案的一部分。在遞回情況下，我們遍歷數字串列，并且在每個迭代步驟（如果尚未使用索引），我們根據當前元素的值（取決于我們是否超過目標）進行一兩次遞回呼叫與否）。一般來說，我們有兩個機會：要么取當前元素，要么忽略它。這些遞回呼叫的結果將相加并產生遞回 case的回傳值。

因為我們需要幾個額外的引數，所以創建一個輔助多載方法（將在客戶端代碼中使用）是一個好習慣，它只需要一個數字串列和一個目標值，并將實際作業委托給遞回方法。

這就是它的樣子。

public static int sumRecursively(List<Integer> numbers, int target) {
    
    return sumRecursively(new ArrayList<>(numbers),
                          new ArrayList<>(),
                          new CombinationTracker(numbers.size()),
                          0, 0, target);
}

實際遞回方法：

private static int sumRecursively(List<Integer> numbers,
                                  List<Integer> combination,
                                  CombinationTracker tracker,
                                  int currentIndex,
                                  int currentSum, int target) {
    
    if (currentSum == target && tracker.allNotUsed(combination)) { // base case - a combination has been found
        tracker.setIsUsed(combination);
        return target;
    }
    
    // recursive case
    int result = 0;
    
    for (int i = currentIndex; i < numbers.size(); i  ) {

        int next = numbers.get(i);

        if (tracker.indexIsUsed(i)) continue;
        if (currentSum   next > target) continue;
        // there are two opportunities for each number: either use next number, or ignore it
        // add next number
        if (next   currentSum <= target) {
            List<Integer> newCombination = new ArrayList<>(combination);
            newCombination.add(i);
            result  = sumRecursively(numbers, newCombination, tracker, i   1, currentSum   next, target);
        }
        // ignore next number
        result  = sumRecursively(numbers, new ArrayList<>(combination), tracker, i   1, currentSum, target);
    }
    return result;
}

main()

public static void main(String[] args) {
    System.out.println(sumRecursively(List.of(1, 3, 4, 5, 6, 6), 12));
    System.out.println(sumRecursively(List.of(6, 6, 6, 6, 6, 6), 12));
}

輸出：

12
36

轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/495647.html

標籤：爪哇列表算法递归组合

上一篇：簡寫` =`是在這個程式中更新變數的唯一方法嗎？[復制]

下一篇：無法從'void'轉換為'System.Collections.Generic.Dictionary<string,bool>'