C ++中具有给定总和的最大大小子集
问题陈述
给定N个元素和总和的数组。我们需要找到总和等于给定总和的最大子集的大小
示例
如果输入数组是arr={2，3，5，10}并且sum=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