數(shù)組最小乘積子集的 JavaScript 程序是計算機科學(xué)和編程領(lǐng)域中出現(xiàn)的常見問題。問題陳述要求我們找到可以從給定數(shù)組的任何子集獲得的最小乘積。
數(shù)組的最小乘積子集是產(chǎn)生最小可能乘積的數(shù)組元素的子集。有多種算法可用于識別該子集，包括動態(tài)規(guī)劃、貪婪算法和分支定界。算法的選擇取決于當(dāng)前問題的特定約束和規(guī)范。
在本教程中，我們將討論使用 JavaScript 編程語言解決此問題的各種方法。我們將介紹基本算法方法及其使用 JavaScript 代碼片段的實現(xiàn)。在本教程結(jié)束時，讀者將清楚地了解問題陳述以及使用 JavaScript 解決問題的各種方法。
問題陳述
給定一個整數(shù)數(shù)組，我們需要找到該數(shù)組的最小乘積子集。數(shù)組的乘積子集定義為數(shù)組的任何子集的乘積。
例如，
讓我們考慮數(shù)組 [2, 3, -1, 4, -2]。
該數(shù)組的產(chǎn)品子集是
[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].
登錄后復(fù)制
該數(shù)組的最小乘積子集是 [-2]。
現(xiàn)在讓我們討論解決此問題陳述的各種算法方法并選擇最適合的算法。
算法
算法的選擇取決于問題的具體限制和先決條件。
貪婪算法 – 貪婪算法是發(fā)現(xiàn)數(shù)組的最小乘積子集的常用方法。其基本概念是從初始數(shù)組元素開始，僅在生成較小的乘積時將下一個元素附加到子集。盡管貪心算法易于實現(xiàn)且簡單，但它不一定能提供最優(yōu)解，而且對于大型數(shù)組，其性能可能會明顯緩慢。
動態(tài)規(guī)劃 – 動態(tài)規(guī)劃是用于解決此問題的另一種算法。它將問題分成較小的子問題，并一次性解決每個子問題，利用較小子問題的解決方案來確定較大子問題的解決方案。這種方法可以節(jié)省大量的時間和空間。雖然動態(tài)規(guī)劃可以保證最優(yōu)解，但它的實現(xiàn)可能比貪心算法更復(fù)雜。
分支定界算法 – 識別數(shù)組的最小乘積子集的另一種方法是分支定界算法。它需要通過分支和限制搜索以僅考慮有效的解決方案來探索多種可能性。該算法保證了最優(yōu)解，并且對于特定場景可以比其他算法更快。盡管如此，它的實現(xiàn)可能更加復(fù)雜，并且可能比其他算法需要更多的時間和空間資源。
總之，一種簡單的方法需要生成所有子集，計算每個子集的乘積，然后返回最小乘積。
更好的解決方案需要考慮以下事實。
第 1 步 – 在沒有零且負數(shù)為偶數(shù)的情況下，除最大負數(shù)之外的所有元素的乘積將產(chǎn)生結(jié)果。
第 2 步 – 在沒有零且負數(shù)為奇數(shù)的情況下，所有元素的乘積將提供結(jié)果。
第 3 步 – 如果存在零且完全為正數(shù)，則結(jié)果為 0。但是，在不存在負數(shù)且所有其他元素均為正數(shù)的特殊情況下，答案應(yīng)該是最小的正數(shù)。
現(xiàn)在讓我們嘗試通過一個使用 JavaScript 實現(xiàn)問題陳述的示例來理解上述方法。
示例
該程序首先計算負數(shù)、零、最大值負數(shù)、最小值正數(shù)以及非零數(shù)的乘積的計數(shù)。然后，它應(yīng)用基于負數(shù)和零的計數(shù)的規(guī)則，以返回數(shù)組的最小乘積子集。程序時間復(fù)雜度為O(n)，輔助空間為O(1)。
輸入1：a[] = { -1, -1, -2, 4, 3 }; n = 5
預(yù)期輸出：最小子集為 [ -2, 4, 3 ]，最小乘積為 -24。
輸入2：a[] = { -1, 0 }; n = 2
預(yù)期輸出：最小子集為 [ -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}.`);
登錄后復(fù)制
結(jié)論
因此，在本教程中，我們學(xué)習(xí)了如何使用 JavaScript 通過遵循簡單的算法來查找數(shù)組的最小乘積子集。該解決方案涉及各種標準，例如數(shù)組中存在的負數(shù)、正數(shù)和零的數(shù)量。它使用簡單的 if-else 條件來檢查這些條件并相應(yīng)地返回最小產(chǎn)品子集。程序時間復(fù)雜度為O(n)，所需輔助空間為O(1)。
以上就是數(shù)組最小乘積子集的 JavaScript 程序的詳細內(nèi)容，更多請關(guān)注www.92cms.cn其它相關(guān)文章！
