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