এই সমস্যায় আমাদের একটি অ্যারে arr[] দেওয়া আছে সাইজ 2n। আমাদের কাজ সাবসেটের ওপর যোগফল বের করার প্রোগ্রাম তৈরি করা ডাইনামিক প্রোগ্রামিং ব্যবহার করে।
আমাদের ফাংশনটি ক্যালকুলেট করতে হবে, F(x) = Σ Ai যাতে x&i == i সব x-এর জন্য। অর্থাৎ i হলো x-এর বিটওয়াইজ সাবসেট।
উদাহরণ:
ইনপুট: A[] = {5, 7, 1, 9} , n = 2
আউটপুট: 5 12 6 22
ব্যাখ্যা: n = 2 হলে x-এর ৪টি মান থাকে। সেগুলো 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
