サブセットの合計-C++での動的計画法

この問題では、サイズ2 ⁿ の配列arr[]が与えられます。 。私たちのタスクは、動的計画法を使用してサブセット全体の合計を見つけるプログラムを作成し、それを解決することです。

関数F（x）=ΣA _iを計算する必要があります すべてのxに対してx＆i==iとなるようにします。つまり、iはxのビット単位のサブセットです。

問題を理解するために例を見てみましょう。

入力： A [] ={5、7、1、9}、n =2

出力： 5 12 6 22

説明： n =2の場合、xには4つの値があります。 0、1、2、3です。

ここで、関数の値を計算します：

F（0）=A ₀ =5
F（1）=A ₀ + A ₁ =5 + 7 =12
F（2）=A ₀ + A ₂ =5 + 1 =6
F（3）=A ₀ + A ₁ + A ₂ + A ₃ =5 + 7 + 1 + 9 =22

動的計画法を使用したこの問題の解決策 マスクを見て、すべてのマスクのビット単位のサブセットを見つけます。動的計画法を使用してビット単位のサブセットを格納します。これにより、繰り返し回数が減ります。設定されたビットまたは設定されていないビットを持つインデックスには、2 ⁿ がアクセスします。 複数回マスクします。

iインデックスのビットに基づいて繰り返します：

i番目のビットが設定されている場合：

DP（mask、i）=DP（mask、i-1）U DP（mask 2 ⁱ 、i-1）

i番目のビットが設定されていない場合：

DP（マスク、i）=DP（マスク、i-1）

ソリューションの動作を説明するプログラム

例

#include <iostream>
using namespace std;
const int N = 1000;

void SumOverSubsets(int a[], int n) {
   
   int sum[1 << n] = {0};
   int DP[N][N];
   for (int i = 0; i < (1 << n); i++) {
      for (int j = 0; j < n; j++) {
         if (i & (1 << j)) {
            if (j == 0)
               DP[i][j] = a[i] + a[i ^ (1 << j)];
            else
               DP[i][j] = DP[i][j - 1] + DP[i ^ (1 << j)][j - 1];
         } else {
            if (j == 0)
               DP[i][j] = a[i];
            else
               DP[i][j] = DP[i][j - 1];
         }
      }
      sum[i] = DP[i][n - 1];
   }
   for (int i = 0; i < (1 << n); i++)
      cout<<sum[i]<<"\t";
}
int main() {
   int A[] = {5, 7, 1, 9};
   int n = 2;  
   cout<<"The sum over subsets is \t";
   SumOverSubsets(A, n);  
   return 0;
}

出力

The sum over subsets is 5 12 6 22