c++仓库中有 n 块狂暴石,每块狂暴石有两个属性:愤怒和暴躁。携带这些狂暴石会获得相应的属性,具体来说:总的愤怒值为所有狂暴石愤怒值之积,总的暴躁值为所有狂暴石暴躁值之和。现在小明想知道,如何选取狂暴石(不能一块都不选),可以使得总愤怒值和总暴躁值相差的最少。现在请你帮帮他,计算出这个相差最小的值。
时间: 2024-04-16 14:28:00 浏览: 31
这个问题可以通过动态规划来解决。我们可以使用一个二维数组dp,其中dp[i][j]表示前i块狂暴石中,总愤怒值和总暴躁值相差为j的最小愤怒值。
首先,我们需要计算出所有狂暴石的愤怒值之积和总暴躁值。然后,我们可以初始化dp数组,将所有元素初始化为无穷大,除了dp[0][0]初始化为0。
接下来,我们可以使用两个循环来填充dp数组。外层循环遍历狂暴石的数量i,内层循环遍历总愤怒值和总暴躁值的差值j。在每次迭代中,我们可以选择将第i块狂暴石放入或不放入选取的集合中。
如果选择放入第i块狂暴石,那么dp[i][j]的值可以通过dp[i-1][j-狂暴石i的暴躁值] + 狂暴石i的愤怒值来更新。如果选择不放入第i块狂暴石,那么dp[i][j]的值可以通过dp[i-1][j]来更新。
最后,我们可以遍历dp[n][j],找到使得总愤怒值和总暴躁值相差最小的j值,即为所求的答案。
以下是一个使用动态规划解决该问题的C++代码示例:
```cpp
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> anger(n);
vector<int> irritability(n);
int totalAnger = 1;
int totalIrritability = 0;
for (int i = 0; i < n; i++) {
cin >> anger[i];
totalAnger *= anger[i];
}
for (int i = 0; i < n; i++) {
cin >> irritability[i];
totalIrritability += irritability[i];
}
int diff = abs(totalAnger - totalIrritability);
vector<vector<int>> dp(n + 1, vector<int>(diff + 1, INT_MAX));
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= diff; j++) {
if (j >= irritability[i-1])
dp[i][j] = min(dp[i-1][j], dp[i-1][j-irritability[i-1]] + anger[i-1]);
else
dp[i][j] = dp[i-1][j];
}
}
int minAngerDiff = INT_MAX;
for (int j = 0; j <= diff; j++) {
minAngerDiff = min(minAngerDiff, abs(diff - 2 * dp[n][j]));
}
cout << minAngerDiff << endl;
return 0;
}
```
希望这个解决方案可以帮助到你!