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