সমস্যা বিবরণ
N সংখ্যক উপাদানের একটি অ্যারে এবং একটি যোগফল দেওয়া আছে। আমাদের কাজ হল সেই সাবসেটের আকার বের করা যার যোগফল দেওয়া যোগফলের সমান এবং আকার সর্বোচ্চ।
উদাহরণ
ইনপুট অ্যারে arr = { 2, 3, 5, 10 } এবং sum = 20 হলে আউটপুট হবে 4 কারণ −
2 + 3 + 5 + 10 = 20 যা দেওয়া যোগফলের সমান।
এল्गরিদম
এই সমস্যা সমাধানের জন্য ডাইনামিক প্রোগ্রামিং ব্যবহার করা যেতে পারে।
সর্বোচ্চ সাবসেট গণনা করার জন্য, আমরা একটি অন্য DP অ্যারে ব্যবহার করব (যাকে 'কাউন্ট অ্যারে' বলা হয়) যেখানে count[i][j] হল নিম্নলিখিত দুটির সর্বোচ্চ মান:
- count[i][j-1]। এখানে বর্তমান উপাদান বিবেচনা করা হয়নি।
- count[i- X][j-1] + 1। এখানে X হল সাবসেটের জন্য নির্বাচিত বর্তমান উপাদানের মান।
উদাহরণ
#include<bits/stdc++.h> using namespace std; int isSubsetSum(int set[], int n, int sum) { bool subset[sum + 1][n + 1]; int count[sum + 1][n + 1]; for (int i = 0; i <= n; i++) { subset[0][i] = true; count[0][i] = 0; } for (int i = 1; i <= sum; i++) { subset[i][0] = false; count[i][0] = -1; } for (int i = 1; i <= sum; i++) { for (int j = 1; j <= n; j++) { subset[i][j] = subset[i][j - 1]; count[i][j] = count[i][j - 1]; if (i >= set[j - 1]) { subset[i][j] = subset[i][j] || subset[i - set[j - 1]][j - 1]; if (subset[i][j]) { count[i][j] = max(count[i][j - 1], count[i - set[j - 1]][j - 1] + 1); } } } } return count[sum][n]; } int main() { int set[] = { 2, 3, 5, 10 }; int sum = 20; int n = 4; cout<< "Result = " << isSubsetSum(set, n, sum) << endl; }
আউটপুট
যখন আপনি উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিচের আউটপুট জেনারেট করবে −
Result = 4
