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

Mô tả bài toán

Cho mảng nums, tìm hai tập con không giao nhau sao cho tổng của chúng bằng nhau và lớn nhất có thể. Trả về giá trị tổng đó.

Ví dụ: nums = [2,5,4,6] → 6 (tập [2,4] và [6]).

Giải thuật (Quy hoạch động)

1. Tổng toàn bộ mảng = sum.
2. dp[i][j] = tổng lớn nhất của tập con đầu tiên khi xét i phần tử đầu và chênh lệch giữa hai tập là j - sum (dịch chuyển chỉ số để tránh âm).
3. Khởi tạo dp[0][sum] = 0.
4. Duyệt i từ 1 đến n, x = nums[i-1]. Cập nhật dp[i][j] từ dp[i-1][j-x] (thêm vào tập 1), dp[i-1][j+x] (thêm vào tập 2), dp[i-1][j] (bỏ qua).
5. Kết quả dp[n][sum].

Ví dụ minh họa (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 solve(vector<int>& nums) {
    return (new Solution())->solve(nums);
}

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

Đầu vào

{2,5,4,6}

Đầu ra

6