數組最小乘積子集的 JavaScript 程序

陣列最小乘積子集的 JavaScript 程式是電腦科學和程式設計領域中出現的常見問題。問題陳述要求我們找到可以從給定數組的任何子集獲得的最小乘積。

陣列的最小乘積子集是產生最小可能乘積的陣列元素的子集。有多種演算法可用於識別該子集，包括動態規劃、貪婪演算法和分支定界。演算法的選擇取決於當前問題的特定約束和規範。

在本教程中，我們將討論使用 JavaScript 程式語言解決此問題的各種方法。我們將介紹基本演算法方法及其使用 JavaScript 程式碼片段的實作。在本教程結束時，讀者將清楚地了解問題陳述以及使用 JavaScript 解決問題的各種方法。

問題陳述

給定一個整數數組，我們需要找到該數組的最小乘積子集。數組的乘積子集定義為數組的任何子集的乘積。

例如，

讓我們考慮陣列 [2, 3, -1, 4, -2]。

該陣列的產品子集是

[2], [3], [-1], [4], [-2], [2, 3], [2, -1], [2, 4], [2, -2], [3, -1], [3, 4], [3, -2], [-1, 4], [-1, -2], [4, -2], [2, 3, -1], [2, 3, 4], [2, 3, -2], [2, -1, 4], [2, -1, -2], [2, 4, -2], [3, -1, 4], [3, -1, -2], [3, 4, -2], [-1, 4, -2], and [2, 3, -1, 4, -2]. 

此數組的最小乘積子集是 [-2]。

現在讓我們討論解決此問題陳述的各種演算法方法並選擇最適合的演算法。

演算法

演算法的選擇取決於問題的具體限制和先決條件。

貪婪演算法 - 貪婪演算法是發現陣列的最小乘積子集的常用方法。其基本概念是從初始數組元素開始，僅在產生較小的乘積時將下一個元素附加到子集。儘管貪心演算法易於實現且簡單，但它不一定能提供最優解，而且對於大型數組，其效能可能會明顯緩慢。

動態規劃 - 動態規劃是用於解決此問題的另一種演算法。它將問題分成較小的子問題，並一次解決每個子問題，利用較小子問題的解決方案來確定較大子問題的解決方案。這種方法可以節省大量的時間和空間。雖然動態規劃可以保證最優解，但它的實作可能比貪心演算法更複雜。

分支定界演算法 - 辨識陣列的最小乘積子集的另一種方法是分支定界演算法。它需要透過分支和限制搜尋以僅考慮有效的解決方案來探索多種可能性。該演算法保證了最優解，並且對於特定場景可以比其他演算法更快。儘管如此，它的實作可能更加複雜，並且可能比其他演算法需要更多的時間和空間資源。

總之，一個簡單的方法需要產生所有子集，計算每個子集的乘積，然後傳回最小乘積。

更好的解決方案需要考慮以下事實。

• 第 1 步 - 在沒有零且負數為偶數的情況下，除最大負數之外的所有元素的乘積將產生結果。

• 第 2 步 - 在沒有零且負數為奇數的情況下，所有元素的乘積將提供結果。

• 第 3 步 - 如果存在零且完全為正數，則結果為 0。但是，在不存在負數且所有其他元素均為正數的特殊情況下，答案應該是最小的正數。

現在讓我們嘗試透過一個使用 JavaScript 實作問題陳述的範例來理解上述方法。

範例

程式首先計算負數、零、最大值負數、最小值正數、非零數的乘積的計數。然後，它應用基於負數和零的計數的規則，以傳回數組的最小乘積子集。程式時間複雜度為O(n)，輔助空間為O(1)。

輸入1：a[] = { -1, -1, -2, 4, 3 }; n = 5

預期輸出：最小子集為 [ -2, 4, 3 ]，最小乘積為 -24。

輸入2：a[] = { -1, 0 }; n = 2

預期輸出：最小子集為 [ -1 ]，最小乘積為 -1。

function minProductSubset(a, n) {
   if (n === 1) {
      return [a[0], a[0]];
   }
   let negmax = Number.NEGATIVE_INFINITY;
   let posmin = Number.POSITIVE_INFINITY;
   let count_neg = 0, count_zero = 0;
   let subsets = [[]];  
   for (let i = 0; i < n; i++) {
      if (a[i] === 0) {
         count_zero++;
         continue;
      }
      if (a[i] < 0) {
         count_neg++;
         negmax = Math.max(negmax, a[i]);
      }
      if (a[i] > 0 && a[i] < posmin) {
         posmin = a[i];
      }
      const subsetsLength = subsets.length;
      for(let j = 0; j < subsetsLength; j++){
         const subset = [...subsets[j], a[i]];
         subsets.push(subset);
      }
   }
   if (count_zero === n || (count_neg === 0 && count_zero > 0)) {
      return [0, 0];
   }
   if (count_neg === 0) {
      return [posmin, posmin];
   }
   const negativeSubsets = subsets.filter(subset => subset.reduce((acc, cur) => acc * cur, 1) < 0);
   let minSubset = negativeSubsets[0];
   let minProduct = minSubset.reduce((acc, cur) => acc * cur, 1);
   for (let i = 1; i < negativeSubsets.length; i++) {
      const product = negativeSubsets[i].reduce((acc, cur) => acc * cur, 1);
      if (product < minProduct) {
         minSubset = negativeSubsets[i];
         minProduct = product;
      }
   }  
   return [minSubset, minProduct];
}
let a = [-1, -1, -2, 4, 3];
let n = 5;
const [minSubset, minProduct] = minProductSubset(a, n);
console.log(`The minimum subset is [ ${minSubset.join(', ')} ] and the minimum product is ${minProduct}.`);

結論

因此，在本教程中，我們學習如何使用 JavaScript 透過遵循簡單的演算法來尋找陣列的最小乘積子集。此解決方案涉及各種標準，例如數組中存在的負數、正數和零的數量。它使用簡單的 if-else 條件來檢查這些條件並相應地傳回最小產品子集。程式時間複雜度為O(n)，所需輔助空間為O(1)。

以上是數組最小乘積子集的 JavaScript 程序的詳細內容。更多資訊請關注PHP中文網其他相關文章！