計數總和大於或等於k的子集的數量

給定具有n個元素的數組，需要計數總和大於或等於k的子集的數量。計數總和大於或等於k的子集的數量

例如ARR [] = {1,5,9,2,3}，K = 16

1 + 5 + 9 + 2 = 17

1 + 5 + 9 + 3 = 18

1 + 5 + 9 + 2 + 3 = 20

5 + 9 + 2 = 16

5 + 9 + 3 = 17

5 + 9 + 2 + 3 = 19

答案是6.

我知道的一種方法是使用位掩碼動態編程，並檢查sum> = k並增加計數。這種方法的問題是N應該非常小，因爲位掩碼涉及指數運行時間。

上述問題是否還有其他有效算法？

在此先感謝。

來源

2017-07-26 Chandan

的元素都是積極的？ – Henry

它可以是兩者的組合。但爲了簡單起見，我們只考慮積極因素 – Chandan

@亨利讓我們考慮只有積極因素 – Chandan

，並使陣列Counts[Sum+1]其中總和爲所有元素
設置Counts[0] = 1，其他元素的總和 - 零
對於以往x=arr[i]掃描從最終計數陣列，並增加這些條目，這可以從現有迄今數額和x組成

if Counts[j - arr[i]] > 0 then //this check might be omitted 
    Counts[j] = Counts[j - arr[i]] + Counts[j]

然後總結非零計數條目j>=k

複雜性是O(Sum * N)

如果可能的和的範圍很大，但可能的和的數量不那麼高（如arr=[1, 2, 3, 100000000, 100000001]陣列），則可以利用記憶化方法，並僅存儲真正現有的變體在圖

實施例：

arr=[1,2,3,5] 
Counts = [1,0,0,0,0,0,0,0,0,0,0,0] 
after arr[0]=1 
Counts = [1,1,0,0,0,0,0,0,0,0,0,0] 
after arr[1]=2 
Counts = [1,1,1,1,0,0,0,0,0,0,0,0] 
after arr[2]=3 
Counts = [1,1,1,2,1,1,1,0,0,0,0,0] 
after arr[3]=5 
Counts = [1,1,1,2,1,2,2,1,2,1,1,1] 

Counts[8] could be composed from 5 and existing Counts[3] with two variants 
1+2+5; 3+5

來源

2017-07-26 06:27:51 MBo

@亨利感謝您糾正 – MBo

如果k和元素值很小，這種方法也可以工作。如果arr中的每個元素都很大，說10^9會怎麼樣。所以所有元素的總和將是n * 10^9。如果我們遍歷整個範圍，程序將永遠運行。 – Chandan

@Chandan你沒有給出問題中的範圍信息。我添加了關於memoization的註釋。 – MBo

一種方法是使用遞歸創建子集並在從原始集合中省略的元素總和大於總數k時停止遞歸，其中total是數組所有元素的總和。

這裏的說明方法的Java代碼：

import java.util.ArrayList; 
import java.util.BitSet; 
import java.util.List; 

public class SubSet 
{ 

    public static void main(String[] args) 
    { 
     Integer[] set = { 1, 5, 9, 2, 3 }; 
     List<List<Integer>> subsets = subsetsK(set, 16); 
     for (List<Integer> subset : subsets) 
     { 
      System.out.println(subset); 
     } 
    } 

    static List<List<Integer>> subsetsK(Integer[] arr, int k) 
    { 
     int t = 0; 
     for (int n : arr) t += n; 

     List<List<Integer>> subsets = new ArrayList<>(); 
     allSubsets(subsets, arr, new BitSet(arr.length), 0, 0, t - k); 
     return subsets; 
    } 

    public static void allSubsets(List<List<Integer>> subsets, Integer[] arr, BitSet off, int pos, int sum, int lim) 
    { 
     if(sum > lim) return; 

     if(pos == arr.length) 
     { 
      subsets.add(toSubset(arr, off)); 
      return; 
     } 

     off.set(pos); 
     allSubsets(subsets, arr, off, pos + 1, sum + arr[pos], lim); 

     off.clear(pos); 
     allSubsets(subsets, arr, off, pos + 1, sum, lim); 
    } 

    static List<Integer> toSubset(Integer[] arr, BitSet off) 
    { 
     List<Integer> ss = new ArrayList<>(); 
     for (int i = 0; i < arr.length; i++) 
     { 
      if (!off.get(i)) 
       ss.add(arr[i]); 
     } 
     return ss; 
    } 
}

輸出：

[5, 9, 3] 
[5, 9, 2] 
[5, 9, 2, 3] 
[1, 5, 9, 3] 
[1, 5, 9, 2] 
[1, 5, 9, 2, 3]

您可以運行/在這裏編輯代碼：Ideone

來源

2017-07-26 07:39:00 SirRaffleBuffle

計數總和大於或等於k的子集的數量

回答

相關問題