数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究子集和 - C++ 中的动态规划
在这个问题中，我们给定一个大小为 2n 的数组 arr[]。我们的任务是创建一个程序，使用动态规划来找到子集的总和。
我们需要计算函数 F(x) = Σ Ai，其中对于所有 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) = 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(mask, i-1) U DP(mask 2i, i-1)
当第 i 位未设置时
DP(mask, i) = DP(mask, 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
更新于： 2021年1月27日
251 次查看
广告