关于c++:动态规划数组等子集和问题总结

1. 是否划分成 2 个相等和的子数组，转化为 0 - 1 背包问题，何为 sum/2，二重循环从大到小遍历

#include <stdio.h>
#include <iostream>
#include<vector>
using namespace std;

bool canPartion(vector<int>nums) {
    int sum = 0;
    for (int i = 0; i < nums.size(); i++) {sum += nums[i];
    }
    if (sum % 2 == 1) {return false;}
    int target = sum / 2;
    vector<int> dp(target + 1, 0);
    for (int i = 0; i < nums.size(); i++) {for (int j = target; j >= nums[i]; j--) {dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]);
        }
    }
    std::cout << dp[target] << " " << target << endl;
    return dp[target] == target;
}
int main()
{vector<int> nums = {1, 5, 11, 5};
    cout << canPartion(nums) << endl;
    return 0;
}

2。是否划分成 k 个和雷同数组，间接递归

#include <stdio.h>
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool dfs(vector<int> &nums, vector<int> &visited, int start, int k, int cur_sum, int target) {if (k == 1) return true;
    if (target < cur_sum) return false;
    if (target == cur_sum) return dfs(nums, visited, 0, k - 1, 0, target);
    for (int i = start; i < nums.size(); i++) {if (visited[i]) continue;
        visited[i] = 1;
        
        if(dfs(nums, visited, i + 1, k, cur_sum + nums[i], target)) {return true;}
        visited[i] = 0;
        
    }
    
    return false;
}
int main()
{vector<int> nums = {4, 3, 2, 3, 5, 2, 1};
    int sum = 0;
    for (auto num : nums) {sum += num;}
    int k = 4;
    if (sum % k !=0) {
        cout <<"error" <<endl;
        return 0;
    }
    std::sort(nums.begin(), nums.end(), greater<int>());
    vector<int> visited(nums.size(), 0);
    cout << dfs(nums, visited, 0, k, 0, sum / k) << " " << sum / k <<endl;
    return 0;
}