এই সমস্যায়, আমাদের একটি পূর্ণসংখ্যা অ্যারে এবং একটি সংখ্যা N দেওয়া আছে। আমাদের কাজ হল অ্যারের উপাদানগুলো যোগ করে N তৈরির মোট পদ্ধতির সংখ্যা গণনা করা। সব কম্বিনেশন এবং রিপিটিশন অনুমোদিত।
একটি উদাহরণ নিয়ে সমস্যাটি বুঝি,
ইনপুট
arr = {1, 3, 5} N = 6
আউটপুট
8
ব্যাখ্যা
পদ্ধতিগুলো হল -
5+1, 1+5, 3+3, 3+1+1+1, 1+3+1+1, 1+1+3+1, 1+1+1+3, 1+1+1+1+1+1
এই সমস্যাটি সমাধান করতে, আমাদের একটি ভিন্ন পদ্ধতি ব্যবহার করতে হবে কারণ সব ধরনের কম্বিনেশন ভিন্ন ভাবে বিবেচিত হবে তাই, যদি সংখ্যাটি অ্যারের ৪টি উপাদানের যোগফল হয় তবে ৪টি ভিন্ন পদ্ধতি বিবেচিত হবে (উদাহরণে দেখানো হয়েছে)। এমন সমস্যা সমাধান করতে, আমাদের ডাইনামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করতে হবে এবং নিচের প্রোগ্রামটি বাস্তবায়ন দেখাবে।
উদাহরণ
#include <iostream> #include <cstring> using namespace std; int arraySumWays(int array[], int size, int N){ int count[N + 1]; memset(count, 0, sizeof(count)); count[0] = 1; for (int i = 1; i <= N; i++) for (int j = 0; j < size; j++) if (i >= array[j]) count[i] += count[i - array[j]]; return count[N]; } int main() { int array[] = {1, 5, 6}; int size = sizeof(array) / sizeof(array[0]); int N = 7; cout<<"মোট পদ্ধতির সংখ্যা যাতে "<<N<<" অ্যারে এলিমেন্টের যোগফলে তৈরি করা যায় "<<arraySumWays(array, size, N); return 0; }
আউটপুট
মোট পদ্ধতির সংখ্যা যাতে ৭ অ্যারে এলিমেন্টের যোগফলে তৈরি করা যায় 6
