给出一段c++代码示例
时间: 2024-09-23 10:00:17 浏览: 20
当然,这里是一个简单的C++代码示例,它演示了如何使用动态规划求解上面提到的分割等和子集问题:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int minAbsDifference(int arr[], int n) {
int totalSum = 0;
for (int i : arr)
totalSum += i;
if (n % 2 == 1) // 如果数组长度为奇数,不可能找到和相同的两个子集
return -1;
vector<int> dp(totalSum / 2 + 1, 0);
dp[0] = 1; // 子集和为0时肯定存在
for (int i = 1; i <= totalSum / 2; ++i) {
for (int j = 0; j < n && arr[j] <= i; ++j) {
dp[i] |= dp[i - arr[j]]; // 动态转移方程
}
}
int minDiff = INT_MAX;
for (int i = totalSum / 4; i <= totalSum / 2; ++i) {
minDiff = min(minDiff, abs(i * 2 - totalSum));
}
return minDiff;
}
int main() {
int arr[] = {1, 4, 2, 3, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum absolute difference is: " << minAbsDifference(arr, n) << endl;
return 0;
}
```
这段代码首先计算数组的总和,然后使用一个二维布尔数组 `dp` 来跟踪每个和是否可行。之后通过迭代计算最小差值,并在主函数中测试该函数。