本文共 1227 字,大约阅读时间需要 4 分钟。
将一个数组分成两部分,不要求两部分所包含的元素个数相等,要求使得这两个部分的和的差值最小。比如对于数组{1,0,1,7,2,4},可以分成{1,0,1,2,4}和{7},使得这两部分的差值最小。
思路:
这个问题可以转化为求数组的一个子集,使得这个子集中的元素的和尽可能接近sum/2,其中sum为数组中所有元素的和。这样转换之后这个问题就很类似0-1背包问题了:在n件物品中找到m件物品,他们的可以装入背包中,且总价值最大不过这里不考虑价值,就考虑使得这些元素的和尽量接近sum/2。
下面列状态方程:
dp[i][j]表示前i件物品中,总和最接近j的所有物品的总和,其中包括两种情况:如果第i件物品没有包括在其中,则dp[i][j] = dp[i-1][j]
如果第i件物品包括在其中,则dp[i][j] = dp[i-1][j-vec[i]]当然,这里要确保j-vec[i] >= 0。
所以状态转移方程为:
dp[i][j] = max(dp[i-1][j],dp[i-1][j-vec[i]]+vec[i]);C++代码实现:
#include#include #include using namespace std;//返回两部分的差值int diff(vector & vec){ int len = vec.size(); int sum = 0; for (int i = 0; i < len; ++i) { sum += vec[i]; } vector > dp; for (int i = 0; i <= len; i++) { vector tmp; for (int j = 0; j <= sum / 2; ++j) { tmp.push_back(0); } dp.push_back(tmp); } for (int i = 1; i <= len; ++i) { for (int j = 1; j <= sum / 2; ++j) { if(j>=vec[i-1])dp[i][j] = max(dp[i-1][j],dp[i-1][j-vec[i-1]]+vec[i-1]); else dp[i][j] = dp[i - 1][j]; } } return sum - 2*dp[len][sum / 2];}int main(){ vector vec = { 1,2,3 ,4,5}; cout << diff(vec) << endl; system("pause"); return 0;}
转载地址:http://nsqxi.baihongyu.com/