資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告