总和子集-C ++中的动态编程
在这个问题中，我们得到了一个大小为2n的数组arr[]。我们的任务是创建一个程序，以使用动态编程来解决子集上的总和。
我们需要计算函数F(x)=ΣAi，使得所有xie的x＆i==i是x的按位子集。
让我们举个例子来了解这个问题，
输入： A[]={5，7，1，9}，n=2
输出：512622
说明：对于n=2，有4个x值。它们是0、1、2、3。
现在，计算函数的值：
F=A0=5
F(1)=A0+A1=5+7=12
F(2)=A0+A2=5+1=6
F(3)=A0+A1+A2+A3=5+7+1+9=22
使用动态编程解决此问题的方法， 我们将查看掩码并找到每个掩码的按位子集。我们将使用动态编程存储按位子集，这将减少重复次数。具有设置位或未设置位的索引将被2n个掩码多次访问。
我们将根据i索引的位重复出现：
当第i位被设置时：
DP(mask,i)=DP（掩码，i-1）UDP（掩码2i，i-1）
当第i位未设置时：
DP(mask,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