মডিউল ১৯_১ঃ সাবসেট সাম টপ ডাউন

আমরা 0-1 knapsack এর ভেরিয়েশনের মধ্যে শুরুতে দেখবো সাবসেট সাম। কিন্তু তার আগে সাবসেট কি এটা একটু জেনে নেই।

সাবসেট (Subset) চিহ্ন, যা ⊂ দ্বারা প্রকাশিত হয়, একটি সেট যে অন্যটির অন্তর্ভুক্ত হয় কিন্তু সেটগুলি একই নয় তা প্রকাশ করে। যেমন, আমাদের যদি সেট A = {1, 2, 3} এবং B = {1, 2, 3, 4, 5} থাকে, তবে এটি A ⊂ B হিসাবে প্রকাশ করা যেতে পারে, যা প্রকাশ করে যে A হলো B এর সাবসেট।

ধরি একটা সেট আছে A = {1,2,3,4}|

এটির সাবসেট গুলো হবেঃ {1,2,3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2},{1,3},{1,4},{2,3},{2,4}.{3.4}.{1},{2},{3},{4},{}

তাহলে আমরা বলতে পারি কোনো সেট এ n টি মেম্বার থাকে তাহলে তার সাবসেট হবে 2^n টি।

এবার আসি আমাদের আসল প্রবলেম এ। আমাদের একটা সেট দেওয়া হবে সাথে একটা সাম দেওয়া হবে। আমাদের ওই সেট এর কোনো সাবসেট এর এলিমেন্ট গুলো যোগ করে ওই সাম বানানো পসিবল কিনা বলতে হবে।

এটা আমরা 0-1 knapsack নইয়ে চিন্তা করলেই করে ফেলতে পারি।

ধরি A = {1,2,4,6}

S = 7

এখানে আমরা প্রথমে ৬ কে সিলেক্ট করবো তারপর তাকে নিয়ে ও না নিয়ে দেখবো। যদি ৬ কে নেই তাহলে আমাদের আর সাম প্রয়োজন ৭-৬ = ১। সেই ক্ষেত্রে ৬ এর পরের এলিমেন্ট ৪ কে আমরা আর নিতে পারবো না। আবার ৪ কে না নিয়ে ২ কেও নিতে পারবো না। ২ কে না নিয়ে ১ কে নিতে পারবো। কারন ৬ কে নেওয়ার পর আমাদের প্রয়োজন ১ আর ১ কে নিলে আমাদের সাম হয়ে যায় ০। তাহলে

এটা আমাদের একটা আন্সার। আবার আমরা ৬ কে না নিয়ে ৪ এর কাছে যেতে পারি। সেই ক্ষেত্রে আমাদের দরকার থাকবে ৭। যদি ৪ কে নেই তাহলে দরকার থাকবে ৭-৪ = ৩। যদি ৪ কে নিয়ে ২ কে নেই তাহলে দরকার থাকবে ৩-২ = ১। আর যদি ১ কে নেই তাহলে দরকার হবে ১-১ = ০। এটাও আমাদের একটা আন্সার।

বাকি অন্য কোনো এলিমেন্ট চুজ করে ৭ পাওয়া সম্ভব নয়।

// Some code
int dp[1005][1005];
bool subset_sum(int n, int a[], int s)
{
    if (n == 0)
    {
        if (s == 0)
            return true;
        else
            return false;
    }
    if (dp[n][s] != -1)
        return dp[n][s];
    if (a[n - 1] <= s)
    {
        bool op1 = subset_sum(n - 1, a, s - a[n - 1]);
        bool op2 = subset_sum(n - 1, a, s);
        return dp[n][s] = op1 || op2;
    }
    else
    {
        return dp[n][s] = subset_sum(n - 1, a, s);
    }
}

এখানে আমরা বেইস কেইস এ যদি কোনো এলিমেন্ট বাকি না থাকে আর আমরা যদি সাম পেয়ে যায় তাহলে true দিচ্ছি আর নাহলে false দিচ্ছি।

এরপর memoization ব্যবহার করছি। যদি কারেন্ট এলিমেন্ট remaining sum এর থেকে ছোট বা সমান হয় তাহলে সেটিকে নিয়ে ও না নিয়ে কি আন্সার পায় চেক করছি। আর যদি বড় হয় তাহলে শুধু না নিয়ে চেক করছি।

সম্পূর্ণ কোডঃ

// Some code
#include <bits/stdc++.h>
using namespace std;
int dp[1005][1005];
bool subset_sum(int n, int a[], int s)
{
    if (n == 0)
    {
        if (s == 0)
            return true;
        else
            return false;
    }
    if (dp[n][s] != -1)
        return dp[n][s];
    if (a[n - 1] <= s)
    {
        bool op1 = subset_sum(n - 1, a, s - a[n - 1]);
        bool op2 = subset_sum(n - 1, a, s);
        return dp[n][s] = op1 || op2;
    }
    else
    {
        return dp[n][s] = subset_sum(n - 1, a, s);
    }
}
int main()
{
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int s;
    cin >> s;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= s; j++)
        {
            dp[i][j] = -1;
        }
    }
    if (subset_sum(n, a, s))
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    return 0;
}