要求：將數組中的數劃分為兩組，使得兩個子數組的和的差值最小，數組中的數的取值范圍為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

總結

以上是生活随笔為你收集整理的将一个数组划分为和差值最小的子数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。