求大牛，请教一个算法问题
2．求西瓜均分问题。（70分）
描述：地面上有12个西瓜，它们的重量（单位为“两”，为计算方便已全部转化为整数，如98即为9斤8两）如下：
98，93，57，64，50，82，18，34，69，56，16，61
（1）设计程序：实现对以上12个瓜“二堆均分”（每堆6个，两堆重量相等），要求打印输出均分的各种可能方案；
（a）输入：数据输入由程序完成，执行程序后不需要任何数据输入；
（b）输出：程序执行后输出以下格式， X分别代表一个西瓜重量的数字，如下：
No1：X X X X X X，X X X X X X
No2：X X X X X X，X X X X X X
……
注：均分的两堆如果只有摆放顺序不一样，算一种输出结果。
（30分）
（2）设计程序，实现对以上12个西瓜，拟实现“三堆均分”（每堆4个，三堆重量相等）。考虑到上述西瓜总重量不能为3所整除，这里另有几个西瓜，重量分别为：70，71，72，73，74，75可供挑选，从12个西瓜中替换掉其中一个，是否可以实现“三堆均分”？如果可以，设计程序实现，要求打印输出均分的各种可能方案；
（a）输入：数据输入由程序完成，执行程序后不需要任何数据输入；
（b）输出：输出结果为以下格式，X分别代表一个西瓜重量的数字，A、B、C、D、E分别代表替换原来西瓜的新重量数字70、71、72、73、74、75，如下 ：
No1（A replaces X）：X X X X，X X X X，X X X X
No2（B replaces X）：X X X X，X X X X，X X X X
……
[解决办法]
还挺复杂的，写了将近一个小时，看来水平下降了！
#include <iostream>using namespace std;#define N 12#define M 6void qsort_one_fun(int a[], int begin, int end){ if (begin<end) { int b=begin; int e=end; int temp=a[b]; while(b<e) { while (b<e && a[e]>=temp) { e--; } a[b]=a[e]; while (b<e && a[b]<=temp) { b++; } a[e]=a[b]; } a[b]=temp; qsort_one_fun(a, begin, e-1); qsort_one_fun(a, e+1, end); } return; }void cnm_sum(int n, int m, int *r){ int lib[999][M]; int pos_lib = 0; int temp[M]; int r_sum = 0; int i; for(i=0; i<n; ++i) { r_sum += r[i]; } int *a = new int[m]; if (a==NULL) { return; } int pos = 0; a[pos] = 0; while (true) { while (!(a[pos]>n-1 || pos>=m-1)) { a[pos+++1] = a[pos] + 1; } if (a[pos]>n-1) { if (pos>0) { a[--pos]++; } else { break; } } else { int sum = 0; while (pos>=0) { sum += r[a[m-1-pos--]]; } if(2*sum==r_sum) { int i; for(i=0; i<m; ++i) { temp[i] = r[a[i]]; } qsort_one_fun(temp, 0, m-1); for(i=0; i<pos_lib; ++i) { int j; for(j=0; j<m && lib[i][j]==temp[j]; ++j); if(j==m) { break; } } if(i==pos_lib) { int j; for(j=0; j<m; ++j) { lib[pos_lib][j] = temp[j]; } ++pos_lib; int pos2 = 0; for(j=0; j<n; ++j) { int k; for(k=0; k<m && j!=a[k]; ++k); if(k==m) { lib[pos_lib][pos2] = r[j]; ++pos2; } } qsort_one_fun(lib[pos_lib], 0, m-1); ++pos_lib; } } a[pos=m-1]++; } } for(i=0; i<pos_lib; ++i) { int j; for(j=0; j<m-1; ++j) { cout<<lib[i][j]<<" "; } cout<<lib[i][j]; if((i&1)==0) { cout<<", "; } if(i>0 && (i&1)==1) { cout<<endl; } }}int main(){ int r[N] = {98,93,57,64,50,82,18,34,69,56,16,61}; cnm_sum(N, M, r); return 0;}
[解决办法]
仅供参考
//给出12个随机数,分成三组求和,每组的个数不定,要求求出来的三个数之间相差最小,最完美的情况是三个数相等.#include <stdlib.h>#include <stdio.h>#include <time.h>#include <math.h>#include <limits.h>int i,j,k;int g[12][3]={//可能的分组大小 { 1, 1,10}, { 1, 2, 9}, { 1, 3, 8}, { 1, 4, 7}, { 1, 5, 6}, { 2, 2, 8}, { 2, 3, 7}, { 2, 4, 6}, { 2, 5, 5}, { 3, 3, 6}, { 3, 4, 5}, { 4, 4, 4},};int n[12];int m[12];int f[12];//当前最小时各数int g1,g2,g3;//1,2,3组可分配的个数int n1,n2,n3;//1,2,3组已分配的个数int f1,f2;//当前最小时1,2组的个数int s1,s2,s3;//123组的和int d;//1-2,2-3,3-1组中各数和之间差的绝对值之和int dmin=INT_MAX;//保存当前d的最小值void swap(int *pi1,int *pi2) { int t; t=*pi1;*pi1=*pi2;*pi2=t;}void test() { s1=0; for (i=0;i<g1;i++) s1=s1+n[i]; s2=0; for (i=g1;i<g1+g2;i++) s2=s2+n[i]; s3=0; for (i=g1+g2;i<12;i++) s3=s3+n[i]; d=abs(s1-s2)+abs(s2-s3)+abs(s3-s1); if (d<dmin) { dmin=d; f1=g1; f2=g2; for (i=0;i<12;i++) f[i]=n[i]; printf("("); for (i=0;i<g1;i++) printf("%2d,",n[i]); printf(") ("); for (i=g1;i<g1+g2;i++) printf("%2d,",n[i]); printf(") ("); for (i=g1+g2;i<12;i++) printf("%2d,",n[i]); printf(") %4d\n",dmin); } else { printf("("); for (i=0;i<g1;i++) printf("%2d,",n[i]); printf(") ("); for (i=g1;i<g1+g2;i++) printf("%2d,",n[i]); printf(") ("); for (i=g1+g2;i<12;i++) printf("%2d,",n[i]); printf(") %4d\n",d); }}void main() { srand(time(NULL)); for (i=0;i<12;i++) m[i]=rand()%100; for (i=0;i<12;i++) printf("%2d,",m[i]); printf("\n"); for (i=1;i<12;i++) { for (j=0;j<i;j++) { if (m[i]>m[j]) swap(&m[i],&m[j]);//冒泡排序从大到小 } } for (i=0;i<12;i++) printf("%2d,",m[i]); printf("\n"); for (k=0;k<12;k++) {//在12种分组方法中 //取第i种分组方法 g1=g[k][0]; g2=g[k][1]; g3=g[k][2]; printf("%2d-%2d,%2d,%2d\n",k,g1,g2,g3); //将从大到小12个数双向轮流分配到三个组中 n1=0; n2=0; n3=0; for (j=0;j<12;j++) { switch (j%6) { case 0: redo: if (n1<g1) { n[n1]=m[j]; n1++; break; } case 1: if (n2<g2) { n[g1+n2]=m[j]; n2++; break; } case 2: if (n3<g3) { n[g1+g2+n3]=m[j]; n3++; break; } case 3: if (n3<g3) { n[g1+g2+n3]=m[j]; n3++; break; } case 4: if (n2<g2) { n[g1+n2]=m[j]; n2++; break; } case 5: if (n1<g1) { n[n1]=m[j]; n1++; break; } default:goto redo; } } test(); } printf("---------------------------------------------------\n"); g1=f1; g2=f2; for (i=0;i<12;i++) n[i]=f[i]; printf("("); for (i=0;i<g1;i++) printf("%2d,",n[i]); printf(") ("); for (i=g1;i<g1+g2;i++) printf("%2d,",n[i]); printf(") ("); for (i=g1+g2;i<12;i++) printf("%2d,",n[i]); printf(") %4d\n",dmin);}