দুটি সেটের সর্বাধিক যোগফল খুঁজে বের করার প্রোগ্রাম যেখানে যোগফল C++ এ সমান

ধরুন আমাদের কাছে সংখ্যা নামক সংখ্যার একটি তালিকা আছে, এখন দুটি সেট খুঁজুন কারণ তাদের যোগফল সমান এবং সর্বাধিক, তারপর যোগফলের মান খুঁজুন।

সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[2, 5, 4, 6], তাহলে আউটপুট 6 হবে, যেমন সেটগুলি [2, 4] এবং [6]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

সমষ্টি :=0
প্রতিটি সংখ্যার জন্য i সংখ্যায়, কর
- সমষ্টি :=যোগফল + i
n :=সংখ্যার আকার
একটি 2D অ্যারে ডিপি আকারের (n + 1) x (2 * যোগফল + 5) সংজ্ঞায়িত করুন এবং -1 দিয়ে পূরণ করুন
dp[0, যোগফল] :=0
আরম্ভ করার জন্য i :=1, যখন i <=n, আপডেট করুন (i 1 দ্বারা বৃদ্ধি করুন), −
- x :=সংখ্যা[i - 1]
- আরম্ভ করার জন্য j :=0, যখন j <2 * যোগফল + 5, আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), করুন −
  - যদি j - x>=0 এবং dp[i - 1, j - x] -1 এর সমান না হয়, তাহলে ^−
    - dp[i, j] :=সর্বাধিক dp[i, j] এবং (dp[i - 1, j - x] + x)
  - যদি j + x <(2 * যোগফল + 5) এবং dp[i - 1, j + x] -1 এর সমান না হয়, তাহলে −
    - dp[i, j] :=সর্বাধিক dp[i, j] এবং (dp[i - 1, j + x])
  - dp[i, j] :=সর্বাধিক dp[i, j] এবং dp[i - 1, j]
রিটার্ন dp[n, sum]

উদাহরণ (C++)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#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 solve(vector<int>& nums) {
   return (new Solution())->solve(nums);
}
main(){
   vector<int> v = {2, 5, 4, 6};
   cout << solve(v);
}

ইনপুট

{2, 5, 4, 6}