C++で指定された合計の最大サイズサブセット

問題の説明

N個の要素と合計の配列が与えられます。合計が与えられた合計に等しい最大サイズのサブセットのサイズを見つける必要があります

例

入力配列がarr={2、3、5、10}でsum =20の場合、出力は-

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