মডিউল ১৯_৬ঃ Minimum Subset Sum

আমরা এখন আরেকটা ভেরিয়েশন দেখবো। সেটা হচ্ছে মিনিমাম সাবসেট সাম।

ধরি A = {1,4,5,11}

তাহলে আমার বের করতে হবে এদের সাবসেট সমূহের মধ্যে মিনিমান সাবসেট সাম কত হবে।

আমরা যদি {১,৪,৫} কে একটা সাবসেট বানায় আর ১১ কে আরেকটা সাবসেট এ নেই তাহলে ডিফারেন্স হবে ১।

এটাও খুব সহজেই করা যায়।

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

ধরি একটা সাবসেটের সাম হচ্ছে = a

আরেকটা সাবসেট এর সাম হচ্ছে = b

আর টোটাল সাম হচ্ছে = s

তাহলে, a+b = s

তাহলে b = s-a

এখন প্রশ্ন আসতে পারে যে আমরা এই একটা সাবসেটের বিভিন্ন সাম গুলো কয় পাবো। আন্সার হচ্ছে সাবসেট সাম এর টেবিল থেকে। সেখানে লাস্ট রো এর দিকে দেখবো। যেসকল সারিতে true পাবো সেগুলোকে আলাদা করে নেবো। তারপর টোটাল সাম থেকে প্রতিবার এক একটা ভ্যালুকে মাইনাস করে দেখবো আর ওই সাবসেট সাম ও এর ডিফারেন্স এর মিনিমাম বের করব।

// Some code
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= s; j++)
        {
            if (dp[i][j] == 1)
                v.push_back(j);
        }
    }
    int ans = INT_MAX;
    for (int val : v)
    {
        int s1 = val;
        int s2 = s - s1;
        ans = min(ans, abs(s1 - s2));
    }
    cout << ans << endl;

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

// Some code
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int a[n], s = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        s += a[i];
    }
    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];
            }
        }
    }
    vector<int> v;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= s; j++)
        {
            if (dp[i][j] == 1)
                v.push_back(j);
        }
    }
    int ans = INT_MAX;
    for (int val : v)
    {
        int s1 = val;
        int s2 = s - s1;
        ans = min(ans, abs(s1 - s2));
    }
    cout << ans << endl;
    return 0;
}