C++ 代码实现 现在有 n 种水果,每一种水果都有一个重量,现在想将这些水果分给两个小朋友,要求这两个小朋友每一个人分到的水果的重量总和相同(个数可以不同,总重量相同即可),剩下的水果就需要丢掉,现在想知道最少需要丢多少重量的水果才能满足要求分给两个小朋友。
时间: 2024-03-03 22:50:28 浏览: 19
以下是C++代码实现,使用动态规划求解:
```c++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> w(n+1); // 水果的重量
int sum = 0; // 总重量
for (int i = 1; i <= n; i++) {
cin >> w[i];
sum += w[i];
}
// 动态规划
vector<vector<int>> dp(n+1, vector<int>(sum/2+1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum/2; j++) {
if (w[i] > j) {
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+w[i]);
}
}
}
int ans = sum - dp[n][sum/2] * 2; // 计算答案
cout << ans << endl;
return 0;
}
```
输入样例:
```
5
1 2 4 6 8
```
输出样例:
```
1
```