資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究C++中具有給定和的最大子集大小
問題陳述
給定一個包含 N 個元素和總和的陣列。我們需要找出最大子集的大小，該子集的和等於給定的總和
示例
如果輸入陣列為 arr = { 2, 3, 5, 10 } 且總和 = 20，那麼輸出將為 4，如下−
2 + 3 + 5 + 10 = 20 等於給定的總和
演算法
我們可以使用動態規劃解決這個問題。
為了計算最大子集，我們使用另一個 DP 陣列（稱為“計數陣列”），其中 count[i][j] 的最大值為。
- count[i][j-1]。此處未考慮當前元素。
- scount[i- X][j-1] + 1。此處 X 是為子集選擇的當前元素的值。
示例
#include<bits/stdc++.h>
using namespace std;
int isSubsetSum(int set[], int n, int sum) {
bool subset[sum + 1][n + 1];
int count[sum + 1][n + 1];
for (int i = 0; i <= n; i++) {
subset[0][i] = true;
count[0][i] = 0;
}
for (int i = 1; i <= sum; i++) {
subset[i][0] = false;
count[i][0] = -1;
}
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {
subset[i][j] = subset[i][j - 1];
count[i][j] = count[i][j - 1];
if (i >= set[j - 1]) {
subset[i][j] = subset[i][j] || subset[i - set[j - 1]][j - 1];
if (subset[i][j]) {
count[i][j] = max(count[i][j - 1], count[i - set[j - 1]][j - 1] + 1);
}
}
}
}
return count[sum][n];
}
int main() {
int set[] = { 2, 3, 5, 10 };
int sum = 20;
int n = 4;
cout<< "Result = " << isSubsetSum(set, n, sum) << endl;
}輸出
當您編譯並執行以上程式時，它將生成以下輸出 −
Result = 4
更新於： 2020-01-21
649 次瀏覽
廣告