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