乘積小于 k 的子集數 · GeeksForGeeks 中文系列教程

# 乘積小于 k 的子集數 > 原文： [https://www.geeksforgeeks.org/number-subsets-product-less-k/](https://www.geeksforgeeks.org/number-subsets-product-less-k/) 給定 n 個元素的數組，您必須找到其元素乘積小于或等于給定整數 k 的子集數。 **示例**： ``` Input : arr[] = {2, 4, 5, 3}, k = 12 Output : 8 Explanation : All possible subsets whose products are less than 12 are: (2), (4), (5), (3), (2, 4), (2, 5), (2, 3), (4, 3) Input : arr[] = {12, 32, 21 }, k = 1 Output : 0 Explanation : there is not any subset such that product of elements is less than 1 ``` **方法**：如果我們通過基本方法來解決此問題，則必須生成所有可能的 2 n 子集，然后對于每個子集，我們必須計算子集元素的乘積并比較給定的產品價值。但是這種方法的缺點是其時間復雜度太高，即 O（n * 2 n ）。現在，我們可以看到它將是指數時間復雜性，在競爭性編碼的情況下應避免這種情況。 **進階方法**：我們將在中間使用[開會的概念。](https://www.geeksforgeeks.org/meet-in-the-middle/) 通過使用這個概念，我們可以降低我們求解 O（n * 2 n / 2 ）的復雜性。 **如何在中間方法中使用 MEET**：首先，我們將給定數組簡單地分為兩個相等的部分，然后我們為數組的兩個部分生成所有可能的子集，并為每個子集存儲元素乘積的值分別分成兩個向量（例如，subset1 & subset2）。現在，這將花費 O（2 n / 2 ）時間復雜度。現在，如果我們對這兩個向量（子集 1 &子集 2）進行排序，每個向量具有（2 n / 2 ）個元素，那么這將花費 O（2 n / 2 * log2 n / 2 ）≈O（n *（2 n / 2 ））時間復雜度。在下一步中，我們遍歷一個具有 2 個 n / 2 個元素的向量 subset1，并在第二個向量中找到 k / subset1 [i]的上限，這將告訴我們乘積小于或等于 k。因此，對于子集 1 中的每個元素，我們將嘗試在子集 2 中以 upper_bound 的形式執行二分搜索，從而再次導致時間復雜度為 O（n *（2 n / 2 ））。因此，如果我們嘗試計算此方法的總體復雜度，則將有 O（n *（2 n / 2 ）+ n *（2 n / 2 ）+ n * （2 n / 2 ））≈O（n *（2 n / 2 ））作為我們的時間復雜度，這比暴力法效率高得多。 **算法**： 1. 將數組分為兩個相等的部分。 2. 生成所有子集，并為每個子集計算元素的乘積并將其推入向量。嘗試數組的兩個部分。 3. 對兩個新向量進行排序，這些向量包含每個可能子集的元素乘積。 4. 遍歷任何一個向量并找到元素 k / vector [i]的上限，以找到元素乘積小于 k 的 vector [i]有多少個子集。 **一些提高復雜性的關鍵點**： * 如果大于 k，則忽略數組中的元素。 * 如果大于 k，則忽略元素乘積以推入向量（子集 1 或子集 2）。 ## C++ ```cpp // CPP to find the count subset having product? // less than k #include <bits/stdc++.h> using namespace std; int findSubset(long long int arr[], int n,? ??????????????????????????????long long int k) { ????// declare four vector for dividing array into? ????// two halves and storing product value of?? ????// possible subsets for them ????vector<long long int> vect1, vect2, subset1, subset2; ????// ignore element greater than k and divide ????// array into 2 halves ????for (int i = 0; i < n; i++) { ????????// ignore element if greater than k ????????if (arr[i] > k) ????????????continue; ????????if (i <= n / 2) ????????????vect1.push_back(arr[i]); ????????else ????????????vect2.push_back(arr[i]); ????} ????// generate all subsets for 1st half (vect1) ????for (int i = 0; i < (1 << vect1.size()); i++) { ????????long long value = 1; ????????for (int j = 0; j < vect1.size(); j++) { ????????????if (i & (1 << j)) ????????????????value *= vect1[j]; ????????} ????????// push only in case subset product is less? ????????// than equal to k ????????if (value <= k) ????????????subset1.push_back(value); ????} ????// generate all subsets for 2nd half (vect2) ????for (int i = 0; i < (1 << vect2.size()); i++) { ????????long long value = 1; ????????for (int j = 0; j < vect2.size(); j++) { ????????????if (i & (1 << j)) ????????????????value *= vect2[j]; ????????} ????????// push only in case subset product is ????????// less than equal to k ????????if (value <= k) ????????????subset2.push_back(value); ????} ????// sort subset2 ????sort(subset2.begin(), subset2.end()); ????long long count = 0; ????for (int i = 0; i < subset1.size(); i++) ????????count += upper_bound(subset2.begin(), subset2.end(),? ?????????????????????????(k / subset1[i])) - subset2.begin(); ????// for null subset decrement the value of count ????count--; ????// return count ????return count; } // driver program int main() { ????long long int arr[] = { 4, 2, 3, 6, 5 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????long long int k = 25; ????cout << findSubset(arr, n, k); ????return 0; } ``` ## Python3 ```py # Python3 to find the count subset? # having product less than k? import bisect def findSubset(arr, n, k):? ????# declare four vector for dividing? ????# array into two halves and storing? ????# product value of possible subsets ????# for them? ????vect1, vect2, subset1, subset2 = [], [], [], []? ????# ignore element greater than k and? ????# divide array into 2 halves? ????for i in range(0, n):? ????????# ignore element if greater than k? ????????if arr[i] > k:? ????????????continue ????????if i <= n // 2:? ????????????vect1.append(arr[i])? ????????else: ????????????vect2.append(arr[i])? ????# generate all subsets for 1st half (vect1)? ????for i in range(0, (1 << len(vect1))):? ????????value = 1 ????????for j in range(0, len(vect1)):? ????????????if i & (1 << j):? ????????????????value *= vect1[j]? ????????# push only in case subset product? ????????# is less than equal to k? ????????if value <= k: ????????????subset1.append(value)? ????# generate all subsets for 2nd half (vect2)? ????for i in range(0, (1 << len(vect2))):? ????????value = 1 ????????for j in range(0, len(vect2)):? ????????????if i & (1 << j):? ????????????????value *= vect2[j]? ????????# push only in case subset product? ????????# is less than equal to k? ????????if value <= k: ????????????subset2.append(value)? ????# sort subset2? ????subset2.sort()? ????count = 0 ????for i in range(0, len(subset1)):? ????????count += bisect.bisect(subset2, (k // subset1[i])) ????# for null subset decrement the? ????# value of count? ????count -= 1 ????# return count? ????return count? # Driver Code if __name__ == "__main__":? ????arr = [4, 2, 3, 6, 5]? ????n = len(arr)? ????k = 25 ????print(findSubset(arr, n, k))? # This code is contributed by Rituraj Jain ``` **輸出**： ``` 15 ``` * * * * * *