我错了。挺晚的了，咱洗洗睡吧。祝你晚安！

我已经知道怎么记录最优解了，如果求0/1背包的算法对的话，明天就能解决这道题

为了完成作业，我也是蛮拼的！
早晨5点就醒了，按昨天的思路对我32楼程序做了修改，可以完成1楼、8楼以及beyondyf版主在67楼提供的实验数据，现提交如下，还请beyondyf
版主帮忙极端测试（要给出我们意想不到的实验数据哦，程序现在可以人为输入实验数据，也可随机产生）：

#include <stdio.h>
#include <stdlib.h>
int sumarry(int *t)
{//统计数组中数据和
    int i,s=0;
    for(i=0;t[i];i++)s+=t[i];
    return s;
}
int lenarry(int *t)
{//得到数组长度
    int i;
    for(i=0;t[i];i++);
    return i;
}
int bag(int *s,int *c,int *t,int p,int w)
{//递归获取最接近袋子容量的组合，s数据源,c存放最接近包容量的数据,t递归得到的所有组合,w包容量
    int i,k,l,m,n;
    k=sumarry(t);l=lenarry(t);
    if((k+s[p])>w)return 0;  //返回0，是发现当前数据和大于包容量，返回上一级循环跳过该数据
    t[l]=s[p];t[l+1]=0;
    m=w-sumarry(c);n=w-sumarry(t);
    for(p++;n<s[p];p++);   //调节源数据指针，减少递归次数
    if(!s[p]&&m<=n)return 3;     //如果数据指针处没有数据则直接返回到主函数的调用者
    if(m>n)
    {//临时集合里的组合最接近包容量则复制到优化的子集合c里
        for(i=0;t[i];i++)c[i]=t[i];
        c[i]=0;m=n;
    }
    if(!m)return 1;        //如果恰好等于包容量直接返回
    for(i=p;s[i];i++)
    {
        n=bag(s,c,t,i,w);  //1为最优解，3直接剪枝，因为改组组合使用完了源数据集合后还没有c里的组合优化
        if(n==1)return n;
        if(n==2)t[l+1]=0;  //剪枝，取下一个数试
        if(n==3)return 2;
    }
    return 2;              //如果是循环完毕则返回到上一级通知剪枝，走下一条回路。
}
void main()
{
    int i,j,k,l,m,n,bc,sc,sw,esw,sb,mw,*p,*c,*t;
    /*备忘：m包容量,n宝藏数量,bc包计数,sc宝藏计数（最终是否有遗漏依据）
            sw宝藏总重,esw装包宝藏总重（检验装包算法）
            sb理想用包数量，mw所需要的平均包容量。
    小于20个宝藏的人为输入，否则电脑随机*/
    while(1)
    {
        m=0;n=0;sw=0;esw=0;
        printf("设置包容量(0退出)：");
        scanf("%d",&m);
        if(m<1)break;
        printf("宝藏数量(多于20个自动输入。0退出)：",m);n=0;
        scanf("%d",&n);
        if(n<1)break;
        p=(int*)malloc(sizeof(int)*(n+1));
        c=(int*)malloc(sizeof(int)*(n+1));
        t=(int*)malloc(sizeof(int)*(n+1));  //申请内存空间
        if(n<20)
        {
            printf("输入%d个宝藏重量（用空格间隔）:",n);
            for(i=0;i<n;i++)scanf("%d",p+i);
        }
        else
            for(i=0;i<n;i++)p[i]=rand()%(m-2)+2;  //产生随机的源数据集合
        p[n]=0;
        for(i=0;i<n;i++)sw+=p[i];  //获取宝藏总重
        sb=sw/m;
        if(sw%m)sb++;   //得到理想用包数量
        mw=sw/sb;
        if(sw%sb)mw++;  //得到在理想包数量情况下平均每个包装包容量
        for(i=0;p[i+1];i++)
        {
            for(j=i+1;p[j];j++)
            {
                if(p[j]>p[i])
                {
                    p[i]^=p[j];
                    p[j]^=p[i];
                    p[i]^=p[j];
                }
            }
        }//冒泡从大到小排序
        for(i=0;p[i];i++)printf("%d,",p[i]);  //输出排序后的源数据
        printf("\n--------------------------------\n");
        bc=0;sc=0; //袋子数量清零,待装包的宝藏数量清零
        while(p[0])
        {
            c[0]=0;  //清除最优解集合数据
            for(i=0;p[i];i++)
            {//开始递归组合，得到c数据
                t[0]=0;  //清除临时集合数据
                l=bag(p,c,t,i,mw);
                if(l==1)break;  //已经得到一组最优解，跳出循环输出最优解
            }
            for(i=0;c[i];i++,sc++)
            {
                l=c[i];
                for(j=0,k=0;p[j];j++)
                {
                    if(p[j]!=l)
                    {
                        p[k]=p[j];
                        k++;
                    }
                    else
                        l=-1;
                }
                p[k]=0;
                printf("%d,",c[i]);  //显示最优子集，从源集合中分离子集
            }
            i=sumarry(c);  //得到当前装包容量
            printf("---%d\n",i);  //显示最优子集单个包装入容量
            esw+=i;
            bc++;  //包的个数递增
            if((sb-bc)>0)
            {
                mw=(sw-esw)/(sb-bc);
                if((sw-esw)%(sb-bc))mw++;  //调整平均包容量
                if(mw>m)mw=m;
            }
            else
                mw=m;
        }
        printf("实际总重%d,装袋总重%d,理想装包数量%d,实际装%d个宝藏用去%d个包\n\n",sw,esw,sb,sc,bc);
        free(p);free(c);free(t);  //释放内存
    }
}

[ 本帖最后由 wmf2014 于 2015-6-13 06:52 编辑 ]

BlueGuy小朋友，加油！
洗衣服去了~~~~~~~~

通过78楼代码和32楼代码对比，用浮动平均数的方式的确比用装满包的方式少用包，在比较包容量1000，宝藏数量1000的情况下，用随机数连续比较3次（没用时间函数，随机数系列不变），最多的一次少用6个包，下图是第一次1000个宝藏的比较结果，少用2个包。

我现在想：把平均数设为single类型，真正做最接近的比较，是不是用的包更少。使用平均数的道理也很简单：你不可能把宝藏剁碎装包，你就只有不断调整让当前装包总数接近平均数。

我的算法跟王姑娘的算法有点区别，我的是直接求组合，
王姑娘是求排列，然后“剪枝”得到组合，王姑娘的算法也是対的，
效率都很低

王姑娘想法是対的，不过代码写不对,
王姑娘的代码复杂度是n! ，我的代码的复杂度是2^n，
所以 王姑娘的代码比我的代码还要慢很多

指望 剪枝 提高速度是不现实的
我还是没看出来这道题目可以动态规划

[ 本帖最后由 BlueGuy 于 2015-6-13 12:11 编辑 ]

我也写了一个，main中主要是输入，算法在put_in_bag函数中

#include<stdio.h>
#include<stdlib.h>

typedef struct Treasure{
    int weight;
    struct Treasure * next;
} Treasure;

int compare_treasure(const void *a, const void *b){ return ((Treasure *)a)->weight - ((Treasure *)b)->weight;}
void put_in_bag(int index);

int n = 0;
int bag_capacity = 0;
Treasure *nodes = NULL; //
Treasure **bags = NULL; //Treasure指针列表，列表以NULL结束

int main(void){
    do {
        printf("input num of treasures:");
        scanf("%d", &n);
        Treasure *pn = realloc(nodes, sizeof(*nodes) * n);
        if (!pn) break;
        nodes = pn;
        Treasure **pa = realloc(bags, sizeof(*bags)*(n+1));
        if (!pa) break;
        bags = pa;
        printf("input capacity of bag:");
        scanf("%d", &bag_capacity);
        getchar();
        printf("随机宝箱重量(y/n default to 'y'):");
        int custom_input = getchar() == 'n';
        if (custom_input)printf("input weight of treasures(<= capacity of bag):");
        int weight;
        for(int i = 0; i < n; ++i){
            if (custom_input)
                scanf("%d", &weight);
            else
                weight = rand() % n + 1;
            if (weight > bag_capacity){
                printf("error weight %d, 必须小于等于包裹容量\n", weight);
                continue;
            }
            nodes[i].weight = weight;
            nodes[i].next = NULL;
        }
        qsort(nodes, n, sizeof nodes[0], compare_treasure); //逆序排列
        for(int i = 0; i < n; ++i)printf("%d ", nodes[i].weight);
        put_in_bag(0);
        for(int i = 0; bags[i]; ++i){
            Treasure *node = bags[i];
            printf("\n%d *** [%d]:", i+1, node->weight);
            for(; node->next; node=node->next)printf("%3d ", node->next->weight);
            free(bags[i]);
            bags[i] = NULL;
        }
        printf("\npress 'q' to quit, others to continue:\n");
        if (custom_input)
            while(getchar() != '\n');
    }while(getchar() != 'q');
    if (nodes) free(nodes);
    if (bags) free(bags);
    return 0;
}

void put_in_bag(int index){
    if (index == n-1){
        Treasure * h = (Treasure *)malloc(sizeof(Treasure)); //头节点
        h->next = &nodes[index];
        h->weight = nodes[index].weight; //头节点的weight表示整个链的总weight
        bags[0] = h;
        bags[1] = NULL;
        return;
    }
    put_in_bag(index + 1);
    Treasure *node = &nodes[index];
    int i = 0;
    for (Treasure *bag = bags[i]; bags[i]; bag = bags[++i]){
        if (bag->weight + node->weight <= bag_capacity){
            node->next = bag->next;
            bag->next = node;
            bag->weight += node->weight;
            break;
        }
    }
    if (!bags[i]){
        Treasure * h = (Treasure *)malloc(sizeof(Treasure)); //头节点
        h->next = node;
        h->weight = node->weight;
        bags[i] = h;
        bags[i+1] = NULL;
    }
}

贴一个测试
input num of treasures:10
input capacity of bag:10
随机宝箱重量(y/n default to 'y'):n
input weight of treasures(<= capacity of bag):2 2 2 2 2 7 7 7 7 7
2 2 2 2 2 7 7 7 7 7
1 *** [9]:  2   7
2 *** [9]:  2   7
3 *** [9]:  2   7
4 *** [9]:  2   7
5 *** [9]:  2   7
press 'q' to quit, others to continue:

你怎么不验证
7
10
5 4 3 2 2 2 2？

这个过不去> <,我再去改改