将一个数组划分为和差值最小的子数组

要求：将数组中的数划分为两组，使得两个子数组的和的差值最小，数组中的数的取值范围为0<X<100，元素个数也是大于0小于100.如：a[]={2,4,5,6,7},得出的两组数：{2，4，6}和{5，7}，abs(sum(a1)-sum(a1))=0;如：{2，5，6，10},abs(sum(2,10)-sum(5,6))=1所以：子数组为：{2,10}和{5,6}。

思路：很容易知道如果选取的某个子数组的和currentSum=sum/2，则这两个子数组的和的差值最小，即从数组中选取某些数字使得其和接近整个数组的1/2.，所以该命题本质上是一个01背包命题，原命题等价于从n各物品中选取若干个，其重量不超过sum/2，且重量达到最大
基于上述思路代码如下：
#include <iostream> using namespace std;const int M = 100; int w[M]; int currentSum[M*M]; bool state[M][M]; int main() {int n;while (scanf("%d ", &n) != EOF) {//输入数组元素个数int sum = 0;for (int i = 0; i < n; ++i) {scanf("%d", &w[i]);sum += w[i];//sum存储整个数组元素的和}memset(currentSum, 0, sizeof(currentSum));memset(state, 0, sizeof(state));for (int i = 0; i < n; ++i)for (int j = sum/2; j >= w[i]; --j) {if (currentSum[j] < currentSum[j-w[i]] + w[i]) {currentSum[j] =currentSum[j-w[i]] + w[i];state[i][j] = true;}}printf("%d\n", sum - currentSum[sum/2]*2);int i = n, j = sum/2;while (i--) {if (state[i][j]) {printf("%d ", w[i]);j -= w[i];}}printf("\n");}return 0; }程序运行结果如下：

转载于:https://www.cnblogs.com/hainange/p/6334064.html

总结

以上是生活随笔为你收集整理的将一个数组划分为和差值最小的子数组的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。