数组分成两个尽量相等的子数组

时间：2025-02-14 14:26:28

类似于0-1背包问题

 

将一个数组分成两部分，不要求两部分所包含的元素个数相等，要求使得这两个部分的和的差值最小。比如对于数组{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的所有物品的总和，其中包括两种情况：

  1. 第i件物品没有包括在其中
  2. 第i件物品包括在其中

如果第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]);

#include ""
#include <iostream>
#include <string>
#include <>
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <algorithm>
#include <sstream>
#include <queue>
#include <iomanip>

using namespace std;

int solution_vivoThird(vector<int> data)
{
	int sum = 0;
	for (int i = 0; i < (); i++)
	{
		sum += data[i];
	}

	vector<vector<int>> dp;
	for (int i = 0; i <= (); i++)
	{
		vector<int> tmp;
		for (int j = 0; j <= sum / 2; j++)
		{
			tmp.push_back(0);
		}
		dp.push_back(tmp);
	}

	for (int i = 1; i <= (); i++)
	{
		for (int j = 1; j <= sum / 2; j++)
		{
			if (j >= data[i - 1])
			{
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - data[i - 1]] + data[i - 1]);
			} else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}

	return sum - 2 * dp[()][sum / 2];
}

int main()
{
	vector<int> data;
	data.push_back(1);
	data.push_back(2);
	data.push_back(3);
	data.push_back(4);
	data.push_back(5);

	int res = solution_vivoThird(data);

	return 0;
}

参考：

[1] /shanshanhi/article/details/67639562

相关文章