用两个循环实现组合

原创文章,转载请注明出处.转载自: Li Haifeng's Blog
本文链接地址: 用两个循环实现组合

来自:richardhuang 对 ACM World Finals 1999-- "Trade on Verweggistan" 的解决


acm world finals 1999解题报告


#include <stdio.h>


#include <iostream.h>


#include <string.h>


main()


{


            int u,n,i,j,k,max,s,total,t,all;


            int a[60][30];


            int b[2000],c[2000];


            int e[300];


            scanf("%d",&n);


            u=0;


            while (n>0)


            {


                            u++;


                            total=0;


                            memset(a,0,sizeof(a));


                            memset(b,0,sizeof(b));


                            b[0]=1;


                            all=0;


                            for (i=1;i<=n;i++)


                            {


                                           scanf("%d",&a[i][0]);


                                           all+=a[i][0];


                                           for (j=1;j<=a[i][0];j++)


                                           {


                                                          scanf("%d",&a[i][j]);


                                           }


                            }/* 读入数据 */


                            for (i=1;i<=n;i++)


                            {


                                           memset(c,0,sizeof(c));


                                           s=0;


                                           max=0;


                                           for (j=1;j<=a[i][0];j++)


                                           {


                                                          s=s+10-a[i][j];


                                                          if (s>max) max=s;


                                           }


                                           s=0;


                                           memset(e,0,sizeof(e));


                                           if (max==0) e[0]=1;


                                           for (j=1;j<=a[i][0];j++)//箱子数


                                           {


                                                          s=s+10-a[i][j];


                                                          if (s==max) e[j]=1;


                                           }


                                           total+=max;


                                           for (j=0;j<=a[i][0];j++)//把每一堆箱子看作一个数组,取第几个箱子把第几个设为1


                                           for (k=0;k<=all;k++)//all是所有的箱子数,把所有箱子也看作数组,从1到all(解空间)


                                           {


                                                          if (b[k]==1 && e[j]==1)


                                                          {


                                                                         c[k+j]=1;//k+j是箱子数的和


                                                          }


                                           }


                                           for (k=0;k<=all;k++)


                                                          b[k]=c[k];


                            }/*递推求解*/


                            printf("Workyards %dn",u);


                            printf("Maximum profit is %d.n",total);


                            printf("Number of pruls to buy:");


                            t=0;


                            for (k=0;k<=all;k++)


                                           if (b[k]==1)


                                           {


                                                          t++;


                                                          printf(" %d",k);


                                                          if (t>=10) break;


                                           }


                            /*输出解答*/


                            printf("nn");


                            scanf("%d",&n);


            }


}


 


///////////////////////////////////////////////////////////////////////


功能:把矩阵每一行的数列出所有组合相加的值,不能出现重复,并从小到大输出


#include <iostream.h>
#include <stdlib.h>
#include <string.h>


int m[5][5]={3,4,7,3,8,
5,6,3,8,4,
2,9,5,3,4,
6,7,8,4,2,
2,9,3,4,2};
int a[100];
int b[100];
int c[10];
void Init()
{
//对a b c初始化
memset(a,0,sizeof(a));//记录正在进行的堆的情况--临时
memset(b,0,sizeof(b));//记录本次以前堆的情况
memset(c,0,sizeof(c));//记录本次的堆的情况
b[0]=1;
}
void main()
{
Init();
for(int i=0;i<5;i++)
{
   memset(c,0,sizeof(c));
   memset(a,0,sizeof(a));
   //把本次运算的数组搞定
   for(int j=0;j<5;j++)
    c[m[i][j]]=1;
   //
   for(int ii=0;ii<10;ii++)
    for(int jj=0;jj<=100;jj++)
    {
     if(b[jj]==1&&c[ii]==1)
      a[ii+jj]=1;
    }
   for(int kk=0;kk<100;kk++)
    b[kk]=a[kk];


}
int num=0;
for(int k=0;k<100;k++)
{
   if(b[k]==1)
   {
    cout<<"第"<<num++<<"个数"<<"t"<<k<<endl;
   }
}
}


From Li Haifeng's Blog, post 用两个循环实现组合

Post Footer automatically generated by wp-posturl plugin for wordpress.

分享到: