数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告