এই সমস্যায়, আমাদেরকে 2 n আকারের একটি অ্যারে অ্যারে দেওয়া হয়েছে . আমাদের কাজ হল এটি সমাধান করার জন্য ডায়নামিক প্রোগ্রামিং ব্যবহার করে উপসেটের যোগফল খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা।
আমাদের ফাংশন গণনা করতে হবে, F(x) =Σ Ai যেমন x&i ==i সব x এর জন্য। অর্থাৎ 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
ডাইনামিক প্রোগ্রামিং, ব্যবহার করে এই সমস্যার সমাধান আমরা মুখোশটি দেখব এবং প্রতিটি মুখোশের একটি বিটওয়াইজ উপসেট খুঁজে বের করব। আমরা ডাইনামিক প্রোগ্রামিং ব্যবহার করে বিটওয়াইজ সাবসেট সংরক্ষণ করব, যা পুনরাবৃত্তির সংখ্যা কমিয়ে দেবে। একটি সূচীতে একটি সেট বিট বা একটি সেট না করা বিট 2
n
দ্বারা পরিদর্শন করা হবে একাধিকবার মুখোশ।
আমরা i সূচকের বিটের উপর ভিত্তি করে পুনরাবৃত্তি করব:
যখন i-th বিট সেট করা হয় :
DP(মাস্ক, i) =DP(মাস্ক, i-1) U DP(মাস্ক 2 i , i-1)
যখন i-th বিট আনসেট থাকে :
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
