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

ให้รายการตัวเลข nums หา 2 เซตที่ผลรวมเท่ากันและมากที่สุด คืนค่าผลรวมนั้น

ตัวอย่าง: nums=[2,5,4,6] → 6 (เซต [2,4] และ [6])

ขั้นตอนการแก้ปัญหา (DP)

1. sum = ผลรวมทั้งหมด
2. dp[i][j] = ผลรวมสูงสุดของเซตแรก เมื่อพิจารณา i ตัวแรก และความต่างระหว่าง 2 เซตคือ j-sum (shift ด้วย sum)
3. dp[0][sum] = 0
4. สำหรับแต่ละตัวเลข x:
   • ใส่เซต 1: dp[i][j] = max(dp[i][j], dp[i-1][j-x] + x)
   • ใส่เซต 2: dp[i][j] = max(dp[i][j], dp[i-1][j+x])
   • ไม่ใส่: dp[i][j] = max(dp[i][j], dp[i-1][j])
5. คำตอบ = dp[n][sum]

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int solve(vector<int>& nums) {
        int sum = 0;
        for (int x : nums) sum += x;
        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 << (new Solution())->solve(v); // 6
    return 0;
}

อินพุต

{2, 5, 4, 6}

เอาต์พุต

6