ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด 2 n . งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมของเซตย่อยโดยใช้การเขียนโปรแกรมแบบไดนามิกเพื่อแก้ปัญหา
เราต้องคำนวณฟังก์ชัน F(x) =Σ Ai ดังนั้น x&i ==i สำหรับ x ทั้งหมด นั่นคือ i เป็นสับเซตระดับบิตของ x
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล: A[] ={5, 7, 1, 9} , n =2
ผลลัพธ์: 5 12 6 22
คำอธิบาย: สำหรับ n =2 มี 4 ค่าของ x คือ 0, 1, 2, 3
ตอนนี้กำลังคำนวณค่าของฟังก์ชัน:
F(0) =A0 =5
F(1) =A0 + A1 =5 + 7 =12
F(2) =A0 + เอ2 =5 + 1 =6
F(3) =A0 + A1 + เอ2 + เอ3 =5 + 7 + 1 + 9 =22
วิธีแก้ปัญหานี้โดยใช้ การเขียนโปรแกรมแบบไดนามิก เราจะดูที่มาสก์และค้นหาเซ็ตย่อยระดับบิตของทุกมาสก์ เราจะจัดเก็บชุดย่อยระดับบิตโดยใช้การเขียนโปรแกรมแบบไดนามิก ซึ่งจะลดจำนวนการทำซ้ำ ดัชนีที่มี set bit หรือ unset bit จะถูกเยี่ยมชมโดย 2
n
มาสก์มากกว่าหนึ่งครั้ง
เราจะเกิดขึ้นอีกตามดัชนีบิตที่ i:
เมื่อตั้งค่าบิต i-th :
DP(หน้ากาก i) =DP(หน้ากาก i-1) U DP(หน้ากาก 2 i , 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
