由n个正整数构成的集合a{ak}, 将其划分为两个不相交的子集a1,a2, 元素个数分别是n1,n2, a1和a2中的元素之和分别是s1,s2。 设计一个尽可能高效的划分算法,满足|n1-n2|最小,且|s1-s2|最大,返回|s1-s2|的结果。 注意:函数头已经给出,只需要写出函数体。
时间: 2023-04-29 09:01:30 浏览: 181
算法思路:
首先将集合a按照从大到小的顺序排序,然后依次将每个元素分配到两个子集中,使得两个子集的元素个数差值最小。具体实现时,可以使用动态规划的思想,设dp[i][j]表示前i个元素分配到两个子集中,使得两个子集元素个数之差为j时,两个子集元素和之差的最大值。则有以下状态转移方程:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-(n1-n2)]+s1-s2, dp[i-1][j+(n1-n2)]+s2-s1)
其中,第一项表示第i个元素不分配到任何一个子集中,第二项表示第i个元素分配到a1中,第三项表示第i个元素分配到a2中。最终的答案即为dp[n][(n1-n2)/2]。
代码实现:
int partition(vector<int>& a) {
int n = a.size();
sort(a.begin(), a.end(), greater<int>());
int sum = accumulate(a.begin(), a.end(), );
vector<vector<int>> dp(n+1, vector<int>(sum/2+1));
for (int i = 1; i <= n; i++) {
for (int j = ; j <= sum/2; j++) {
dp[i][j] = dp[i-1][j];
if (j >= a[i-1]) {
dp[i][j] = max(dp[i][j], dp[i-1][j-a[i-1]]+a[i-1]);
}
if (j <= sum/2-a[i-1]) {
dp[i][j] = max(dp[i][j], dp[i-1][j+a[i-1]]-a[i-1]);
}
}
}
return sum-dp[n][sum/2]*2;
}
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)