数组元素组合，求方法

Question

问题：假设积木的宽和高均一致，仅长度不同
输入：第一行为积木数量N[1,30]
第二行是N个整数，表示各积木的长度[1,100]
输出：最多可叠成多少层等长的积木墙

例1：
输入：
5
2 3 5 4 1
输出：
3
说明：2和3做第一层，5做第二层，4和1做第三层；最多可叠成3层长度为5的积木墙。

例2：
输入：
3
1 2 4
输出：
1
说明：1/2/4三块积木叠成1层长为7的积木墙。

Answer 1

#include <math.h>
#include <string.h>
//冒泡排序
void bubbleArr(int arr[],int len)
{
    for (int i = 0; i < len - 1; i++)
    {
        for (int j = 0; j < len - i - 1; j++)
        {
            if (arr[j] > arr[j + 1]) 
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

//计算整数的所有因子
void calcYZ(int sum,int *yz,int &num)
{
	int i=0;
	num = 0;
	for(i=1;i<sqrt((double)sum);i++)
	{
		if(sum%i==0)
		{
			yz[num++] = i;
			yz[num++] = sum/i;
		}
	}
}

int main()
{
	int n,i,j,a,sum=0;
	printf("请输入数字个数：");
	scanf("%d",&n);
	int *p = new int[n];
	printf("请输入%d个数字：",n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&p[i]);
		sum += p[i];
	}
	//计算所有因子
	int yz[1000] = {0};
	int num = 0;
	calcYZ(sum,yz,num); 
	bubbleArr(yz,num); //对因子进行冒泡排序
	
	for(i=0;i<num;i++) //对每个因子进行遍历检查
	{
		int k = yz[i]; //每层的数值
		int m = sum/k; //层数
		if(m>n) //如果层数比输入数字数量还多，显然不可能成立
			continue;
		int *q = new int[m]; //当前每层已经填入的数值，不能超过k
		memset(q,0,m*sizeof(int));
		for(j=0;j<n;j++) //遍历每个数字，加入到可以填入的层中
		{
			for(a=0;a<m;a++) //遍历所有的层， 检查是否有合适的层可以加入这个数值
			{
				if(q[a] == k) //如果该层值已经是k，则不可以加入，继续检索
					continue;
				if(q[a] < k && (q[a] + p[j]) <=k)   //如果层值小于看且加入新值后不溢出，将数值加入该层
				{
					q[a] += p[j];
					break;
				}
			}
		}
		for(a=0;a<m;a++) //检查是否所有层的值是否都等于k，是则当前层次即为最优层次
		{
			if(q[a] != k)
			{
			
				break;
			}
		}
		delete []q;
		if(a==m) //满足条件
		{
			printf("最多的积木墙层数为：%d\n",m);
			break;
		}

	}

	delete []p;


	return 0;
}