โปรแกรมหาผลรวมสูงสุดของสองชุดที่ผลรวมเท่ากันใน C++

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums ตอนนี้ให้หาสองชุดเนื่องจากผลรวมเท่ากันและสูงสุด จากนั้นหาค่าผลรวม

ดังนั้น หากอินพุตเป็น nums =[2, 5, 4, 6] เอาต์พุตจะเป็น 6 เนื่องจากเซตคือ [2, 4] และ [6]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ผลรวม :=0
• สำหรับแต่ละตัวเลข i เป็น nums ทำ
  • sum :=sum + i
• n :=ขนาดของ nums
• กำหนดขนาดอาร์เรย์ 2 มิติหนึ่ง dp (n + 1) x (2 * ผลรวม + 5) และเติมด้วย -1
• dp[0, ผลรวม] :=0
• สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
  • x :=nums[i - 1]
  • สำหรับการเริ่มต้น j :=0 เมื่อ j <2 * sum + 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, ผลรวม]

ตัวอย่าง (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}

ผลลัพธ์

6