将重量分成两辆卡车的分类任务(C++) (动态规划)

#include <iostream>
#include <vector>

bool canPartition(vector<int>& nums) {
    int n = nums.size();
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    if (sum % 2 != 0) {
        return false;
    }
    int target = sum / 2;
    
    vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
    for (int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= target; j++) {
            if (nums[i - 1] > j) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
    }
    
    return dp[n][target];
}

int main() {
    vector<int> nums = {1, 5, 11, 5};
    if (canPartition(nums)) {
        cout << "可以将重量分成两辆卡车的分类任务" << endl;
    } else {
        cout << "无法将重量分成两辆卡车的分类任务" << endl;
    }
    
    return 0;
}