用两个循环实现组合
来自：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 %d\n",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("\n\n"); 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;
}
}
}
评论
发表评论