মডিউল ১৯_২ঃ সাবসেট সাম Bottom up

আমরা এখন সাবসেট সাম এর Bottom up এপ্রোচটা দেখবো। ট্যাবুলার ফরম্যাট এ এই জিনিস্টা নিয়ে চিন্তা করব।

প্রথমে ধরি,

A = {1,2,3,6}

S = 7

আমাদের কাছে A একটি সেট ও সাম ৭।

তাহলে

তাহলে এখানে ইনিশিয়ালি ফার্স্ট রো ও কলাম ইনিশিয়ালাইজ করে ফেলি। এখানে প্রথম কলাম অবশ্যই true হবে কেননা যেকোনো এলিমেন্টকে চুজ না করে আমরা ০ বানাইতে পারি। আর প্রথম সারি false হবে কেননা কোনো কিছুকে চুজ না করে আমরা 0 এর বড় সংখ্যা বানাইতে পারি না।

তারপর ১,১ ঘরে true হবে কেননা প্রথম এলিমেন্টকে চুজ করে আমরা ১ বানাইতে পারি। ১,২ থেকে শুরু করে ১,৭ অব্দি false হবে কেননা প্রথম এলিমেন্ট ১ কে চুজ করে ১ এর বেশি বড় সংখ্যা বানানো সম্ভব না।

এবার ২,১ থেকে শুরু করে ২,৩ পর্যন্ত true হবে। কেননা প্রথম দুইটা ভ্যালু চুজ করে আমরা ৩ অব্দি সাম বানাইতে পারবো। তাই ৩ অব্দি সব true| এরপর ২,৪ হতে ২,৭ অব্দি সব false|

এবার ৩,১ থেকে শুরু করে ৩,৬ পর্যন্ত true হবে। কেননা প্রথম তিনটা ভ্যালু চুজ করে আমরা ৬ অব্দি সাম বানাইতে পারবো। তাই ৩ অব্দি সব true| এরপর ৩,৭ false|

এবার ৪,১ থেকে শুরু করে ৪,৭ পর্যন্ত true হবে। কেননা প্রথম ৪টা ভ্যালু চুজ করে ৭ অব্দি বানানো সম্ভব।

ইনিশিয়ালাইজ পার্টঃ

// Some code
    dp[0][0] = true;
    for (int i = 1; i <= s; i++)
    {
        dp[0][i] = false;
    }

যদি সাম এ্যারে এর কারেন্ট এলিমেন্ট সাম থেকে ছোট বা সমান হয় তাহলে সেই এলিমেন্ট সহ বা সেটা বাদে অপশনকে কন্সিডার করবো। আর নাহলে সেটা বাদে অপশনকে নিব।

// Some code
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= s; j++)
        {
            if (a[i - 1] <= j)
            {
                dp[i][j] = dp[i - 1][j - a[i - 1]] || dp[i - 1][j];
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
    

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