সি++-এ সমান ও সর্বোচ্চ যোগফল دار দুটি সেট খুঁজে বের করা

সমস্যা বিবরণ

একটি সংখ্যার তালিকা nums দেওয়া আছে। দুটি সেট বানাতে হবে যাতে তাদের যোগফল সমান হয় এবং সেই যোগফলটি সর্বোচ্চ হয়। সেই যোগফলটি রিটার্ন করুন।

উদাহরণ: nums = [2, 5, 4, 6] → আউটপুট 6 (সেট: [2,4] এবং [6])।

সমাধানের পদ্ধতি

ডাইনামিক প্রোগ্রামিং (সাবসেট সম দিয়ে পার্টিশন):

1. sum = সব উপাদানের যোগফল।
2. dp[i][j] = প্রথম iটি উপাদান ব্যবহার করে ডিফারেন্স j - sum অর্জন করা সম্ভব কিনা এবং সেটের যোগফল।
3. অফসেট sum ব্যবহার করে নেগেটিভ ডিফারেন্স হ্যান্ডেল করুন।
4. ট্রানজিশন: উপাদান x কে সেট ১-এ দাও, সেট ২-এ দাও, বা কাউন্ট নাও।
5. dp[n][sum] রিটার্ন করুন।

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(vector<int>& nums) {
        int sum = 0;
        for (int i : nums) sum += i;
        int n = nums.size();
        vector<vector<int>> dp(n+1, vector<int>(2*sum+5, -1));
        dp[0][sum] = 0;
        for (int i = 1; i <= n; i++) {
            int x = nums[i-1];
            for (int j = 0; j < 2*sum+5; j++) {
                if (j-x >= 0 && dp[i-1][j-x] != -1)
                    dp[i][j] = max(dp[i][j], dp[i-1][j-x] + x);
                if (j+x < 2*sum+5 && dp[i-1][j+x] != -1)
                    dp[i][j] = max(dp[i][j], dp[i-1][j+x]);
                dp[i][j] = max(dp[i][j], dp[i-1][j]);
            }
        }
        return dp[n][sum];
    }
};

int main() {
    vector<int> v = {2, 5, 4, 6};
    cout << solve(v);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: {2, 5, 4, 6}

আউটপুট: 6