Chương trình tìm tổng lớn nhất của hai tập hợp có tổng bằng nhau trong C ++

Giả sử chúng ta có một danh sách các số được gọi là num, bây giờ hãy tìm hai tập hợp vì tổng của chúng giống nhau và lớn nhất, sau đó tìm giá trị tổng.

Vì vậy, nếu đầu vào là nums =[2, 5, 4, 6], thì đầu ra sẽ là 6, vì các bộ là [2, 4] và [6].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sum:=0
• đối với mỗi số tôi trong số, thực hiện
  • sum:=sum + i
• n:=kích thước của nums
• Xác định một dp mảng 2D có kích thước (n + 1) x (2 * sum + 5) và điền vào -1
• dp [0, sum]:=0
• để khởi tạo i:=1, khi i <=n, cập nhật (tăng i lên 1), thực hiện -
  • x:=nums [i - 1]
  • để khởi tạo j:=0, khi j <2 * sum + 5, cập nhật (tăng j lên 1), thực hiện -
    • nếu j - x> =0 và dp [i - 1, j - x] không bằng -1, thì ^ -
      • dp [i, j]:=tối đa của dp [i, j] và (dp [i - 1, j - x] + x)
    • nếu j + x <(2 * sum + 5) và dp [i - 1, j + x] không bằng -1, thì -
      • dp [i, j]:=tối đa của dp [i, j] và (dp [i - 1, j + x])
    • dp [i, j]:=tối đa là dp [i, j] và dp [i - 1, j]
• trả về dp [n, sum]

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

{2, 5, 4, 6}

Đầu ra

6