সমস্যা বিবৃতি
N উপাদান এবং যোগফল একটি অ্যারে দেওয়া. আমাদের সর্বাধিক আকারের উপসেটের আকার খুঁজে বের করতে হবে যার যোগফল প্রদত্ত যোগফলের সমান
উদাহরণ
যদি ইনপুট অ্যারে হয় arr ={ 2, 3, 5, 10 } এবং sum =20 তাহলে আউটপুট হবে 4 হিসাবে −
2 + 3 + 5 + 10 =20 যা প্রদত্ত যোগফলের সমান
অ্যালগরিদম
এই সমস্যা সমাধানের জন্য আমরা ডাইনামিক প্রোগ্রামিং ব্যবহার করতে পারি।
সর্বাধিক উপসেট গণনা করতে, আমরা অন্য একটি DP অ্যারে ব্যবহার করি (যাকে বলা হয় 'কাউন্ট অ্যারে') যেখানে গণনা[i][j] সর্বাধিক।
- গণনা[i][j-1]। এখানে বর্তমান উপাদান বিবেচনা করা হয় না।
- scount[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
