Question

求c，c++高手帮忙解决一道题，谢谢了

这道题我以其他形式描述过，有高手帮我解决了，但是总感觉不是最佳方案，所以重新问一下，求高手帮忙解决了，把以前高手做出来的做下优化也行，谢谢了。下面是题
有n个数，这些数全部都是大于0小于6000的数，现在把这些数当成体积块，往6000大小里的容器里放，把容器放满不能再放为止，看最少用多少个6000大小的容器，这里有一个容器里放的体积块可以是任意，其他一定要最大，容器数一定要最少，可以输入一组数验证一下，求高手帮忙给写个，谢谢了

Answer 1

#include <stdio.h>
#include <malloc.h>

typedef struct ele //用来保存容器存入的数字编号
{
	int vno;
	struct ele *link; 
}ELE;
typedef struct hnode //用来保存容器的情况
{
	int remainder;
	ELE *head; 
	struct hnode *next;
} HNODE;

void main()
{
	int n, i, box_count, box_volume, *a;
	HNODE *box_h, *box_t, *j; 
	ELE *p, *q;
	// 输入信息
	printf("输入容器容量: ");
	scanf("%d", &box_volume); 
	printf("输入数字个数: ");
	scanf("%d", &n);
	a = (int *)malloc(sizeof(int)*n);
	i = 0;
	printf("请各数字: ");
	while(i < n) scanf("%d", (a + i++));
	// 贪婪法处理过程，贪婪法不是最优的，但是最快的
	box_h = box_t = NULL;
	box_count = 0;
	for(i = 0; i < n; i++)
	{
		p      = (ELE *)malloc(sizeof(ELE));
		p->vno = i;
		for(j = box_h; j != NULL; j = j->next) if (j->remainder >= a[i]) break; // 找合适的箱子
		if (j == NULL) // 没有找到合适的
		{
			j = (HNODE *)malloc(sizeof(HNODE)); // 新增一个箱子
			j->remainder = box_volume - a[i];
			j->head = NULL;
			if (box_h == NULL) box_h = box_t = j; // 第一个箱子
			else box_t = box_t->next = j;
			j->next = NULL;
			box_count++;
		}
		else j->remainder -= a[i]; // 找到后，将剩余空间减去
		for (q = j->head; q != NULL && q->link != NULL; q = q->link); //保存物品编号
		if (q == NULL)
		{
			p->link = j->head;
			j->head = p;
		}
		else
		{
			p->link = NULL;
			q->link = p;
		}
	}
	// 输出结果
	printf("共使用了%d只容器", box_count); 
	printf("各容器装数字情况如下:\n");
	for (j = box_h, i = 1; j != NULL; j = j->next, i++)
	{
		printf("第%2d只容器，还剩余容量%4d，所装数字编号有:\n\t", i, j->remainder);
		for (p = j->head; p != NULL; p = p->link) printf("%4d", p->vno + 1);
		printf("\n");
	} 
}

追问

请问能帮忙优化一下吗，万分谢谢了

所装数字应该显示的是每个数值啊，余量应该是6000减去这些数值的结果啊，还有，余量不可能是负值的啊

追答

长度超出了，上传个附件，内容在附件中

追问

输入这行数值后按回车怎么老是闪退 啊

能加上你聊吗谢谢了

追答

我自己调试过，没有闪退的现象呀

追问

我用了60个数据啊，已经私信你了，请你看一下，一般用的数据都比较多的，几百个数据也是有可能的

追答

手工输入没有试过，试过随机产生几百个数据的

追问

总容量6000， 个数6 ，5800 600 400 2800 3500 1000，就闪退了

追答

// 删除动态分配的内存

delS(type);

delS(type+1);

free(a);

system("pause");//加上这句

追问

我先采纳你了，我们私信聊好吗，谢谢你了

追答

最优解需要动态规划，这个还不熟悉，不好意思

Answer 2

贪心算法求最优解。很遗憾帮不到你。

追问

要尝试一下吗，我可以把原来的描述和高手做的答案发给你，试试吧

追答

不了，对于算法我接触的比较少，如果已经有了完整的思路，我倒是可以把他实现。

Answer 3

“这里有一个容器里放的体积块可以是任意，其他一定要最大”这句啥意思啊？

追问

一个容器可以不用放满，别的必须放满啊，要求用的容器数最少

追答

...那堆数代表的体积块是可以拆开放……？
那把所有数加起来除以6000向上取证不就完了……？

追问

不能拆开放，每个体积块就是一个体积块，放进6000的容器里面放到不能再放就算放满了，有一个容器不用放满，求容器数最少，能加上聊吗

追答

n多大……

追问

n值任意，但是大点应该比较能看出效果的。