返回信息流有一堆厚度不同的砖，要将它们分成两堆，使两堆砖摞起来高度相等，求分法
这是一条镜像帖。来源：北邮人论坛 / cpp / #44432同步于 2010/10/3
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
求助一道算法题
maijian
2010/10/3镜像同步6 回复
订阅后，新回复会通过你的通知中心匿名送达。
6 条回复
1.先把砖按照厚度排序，存在数组a[]中，计算所有转的厚度和为2*sum,则问题转化为分出一堆砖，其厚度和为sum.
2.初始化数组result[]存放选出的砖的序号，result初始化为0,如果第i块砖被选中，则result[i]置为1.
3. 大概用下面这个函数求就行了。
void Find(int a[], int result[], int sum)
{
for i from(result[] where result[i]=0)
{
if(sum-a[i]==0)
{
result[i]=1;
return;
}
else
{
Find(a, result, sum-a[i]);
}
}
}
这种方法我也想到了，我想知道有没有更好的算法
【 在 yyjkdnsy 的大作中提到: 】
: 1.先把砖按照厚度排序，存在数组a[]中，计算所有转的厚度和为2*sum,则问题转化为分出一堆砖，其厚度和为sum.
: 2.初始化数组result[]存放选出的砖的序号，result初始化为0,如果第i块砖被选中，则result[i]置为1.
: 3. 大概用下面这个函数求就行了。
: ...................
随便写了个 没认真测试 可能有bug 但思路应该是对的:)
#define HEIGHT_MAX 100
#define LEN_MAX 100
int res[HEIGHT_MAX][LEN_MAX]; //存放结果
int a[] = {-1, 1, 2, 1, 2, 1, 1, 2, 2}; //元素0只是占位符，不算在内
int h, l;
for (h = 1; h <= 6; h++) //边界条件
res[h][0] = 0;
for (l = 0; l <= 8; l++) //边界条件
res[0][l] = 1;
for (h = 1; h <= 6; h++) //开始计算
for (l = 1; l <= 8; l++) {
if (h < a[l])
res[h][l] = res[h][l - 1];
else res[h][l] = res[h - a[l]][l - 1]? res[h - a[l]][l - 1] : res[h][l - 1];
}
时间空间都是O(h*l)