一天？你真解不出来。这么着吧，一个礼拜你能解出来，我送你一千专家分。

就上面的各位中，只有rjsp知道了问题所在，但好像还没有适合的解决方案。其他人都是在猜而已，要么想法不对，要么是有生之年都得不到结果的办法。

大周末的还这么热闹。7楼的思路是很普通的，但没考虑到包的利用率。
纯搞编程的同学不一定能解决这个问题。任何问题都可能遍历得到解，但时间是最大的敌人，优化解可以缩短时间，但不是最优解。
功夫远在编程之外
求优化解虽然是以前学这专业的内容，遗憾是没搞这个方向。想用遗传算法甚至没有实现如何表示解的形式。还有待考虑。
如果纯粹靠遍历递归来做，建议如果背包容量为n，考虑把宝藏首先尽量多的装满若干个n。剩下的尽量装。

最近事儿多，还想完善javascript里的五子棋人机对下部分呢，这个这么费脑子的东东本没打算做哦。只是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;
}
void bag(int *s,int *c,int *t,int p,int w)
{//递归获取最接近袋子容量的组合，s数据源,c存放最接近包容量的数据,t递归得到的所有组合,w包容量
    int i,j,k,l,m,n;
    k=sumarry(t);l=lenarry(t);
    if((k+s[p])<=w){t[l]=s[p];t[l+1]=0;}
    for(i=p+1;s[i];i++){bag(s,c,t,i,w);t[l]=0;}
    k=w-sumarry(c);l=lenarry(c);m=w-sumarry(t);n=lenarry(t);
    if(k>m||(k==m&&l<n))
    {//如果递归的数据容量比c里面的数据更接近包容量则交换数据（相等则取数据项目多的）
        for(j=0;t[j];j++)c[j]=t[j];
        c[j]=0;
    }
}
void main()
{
    int i,j,n,m,bc,*p,*c,*t;
    while(1)
    {
        printf("输入宝藏数量：");n=0;
        scanf("%d",&n);
        if(n<=0)break;
        p=(int*)malloc(sizeof(int)*(n+1));
        c=(int*)malloc(sizeof(int)*(n+1));
        t=(int*)malloc(sizeof(int)*(n+1));
        printf("输入宝藏：");
        for(i=0;i<n;i++)
        {
            scanf("%d",p+i);
            c[i]=t[i]=0;
        }
        p[n]=0;
        printf("输入袋子袋子容量：");
        scanf("%d",&m);
        bc=0;//袋子数量清零
        while(p[0])
        {
            for(i=0;i<=n;i++)c[i]=0;//初始化最接近包容量的数据
            for(i=0;p[i];i++)
            {//开始递归组合，得到c数据
                for(j=0;j<=n;j++)t[j]=0;
                bag(p,c,t,i,m);
            }
            for(i=0;c[i];i++)
            {
                for(j=0;p[j]!=c[i]&&p[j];j++);
                p[j]=-1;  //对c里面出现的数据在p里面做标记，好分离子集合
                printf("%d,",c[i]); 
            }
            printf("\n");
            for(i=0,j=0;p[i];i++)
            {
                if(p[i]>0)
                {
                    p[j]=p[i];
                    j++;  //将子集合c从源集合p里分离，直到源集合没有数据，结束。
                }
            }
            p[j]=0;bc++;
        }
        printf("需要%d个包\n",bc);
        free(p);
        free(c);
        free(t);
    }
}

 

这就是一个0/1 背包，网上PPT 一大把，
我很早以前学过，那时不是我自己推导的，所以忘了，
我自己推倒过多重背包，

平时没什么时间解题，端午节肯定有时间了，
端午节，我把题目解出来，你申请把版主让给我

这个帖子我看出来王姑娘 和 林姑娘的水平了
我记得0/1背包是教科书中的例题，

[ 本帖最后由 BlueGuy 于 2015-6-8 07:27 编辑 ]

我不需要你的，我需要beyondf的

这要就是个01背包，还值1000分么？

也活跃一下气氛，1000分的悬赏一周内有效（6月15日0时之前）。分数全归第一个提交正确代码的朋友。

关于“正确”请重回一楼看题，注意要能做到题目要求的范围。并且对于n = 1000的数据自己进行测试，运行时间超过3秒的就别提悬赏的事了（当然，可以交流）。

最近我上网时间不定，如果我长期没有回应请留站内短消息提醒我。

哈哈，又改端午节了？再饶你一天，父亲节前能搞定就行，要求同上。

当然，如果别人先你之前做出来了，专家分就不能给你了。版主让给你没问题，现在都可以，只是不知道如何操作。再者让给你好像意义也不大，我又不能让你连任

没有考虑时间，过了25个数就像死机了。
可能首先要对数组从大到小排序，其次，不需要对全部数据排列，只需要对<=m-c[i]的数据集合进行组合即可。抽空按这个思路试试。

分清楚递归返回的几种情况，不断调整袋子容量，以及缩小集合，极大地提高了速度，1000个数据瞬间完成，修改后的代码如下，不知道正确否（修改完结）：

#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);
    if(m>n)
    {//临时集合里的组合最接近包容量则复制到优化的子集合c里
        for(i=0;t[i];i++)c[i]=t[i];
        c[i]=0;m=n;
    }
    if(!m)return 1;        //如果恰好等于包容量直接返回
    for(p++;n<s[p];p++);   //调节源数据指针，减少递归次数
    if(!s[p]&&sumarry(t)!=sumarry(c))return 3;     //如果数据指针处没有数据则直接返回到主函数的调用者
    for(i=p;s[i];i++)
    {
        n=bag(s,c,t,i,w);  //1为最优解，3直接剪枝，因为改组组合使用完了源数据集合后还没有c里的组合优化
        if(n==1||n==3)return n;
        if(n==2)t[l+1]=0;  //剪枝，取下一个数试
    }
    return 2;              //如果是循环完毕则返回到上一级通知剪枝，走下一条回路。
}
void main()
{
    int i,j,k,l,m,n,bc,sc,*p,*c,*t;
    while(1)
    {
        m=45;
        printf("袋子容量为%d,输入宝藏数量(0退出)：",m);n=0;
        scanf("%d",&n);
        if(n<=0)break;
        p=(int*)malloc(sizeof(int)*(n+1));
        c=(int*)malloc(sizeof(int)*(n+1));
        t=(int*)malloc(sizeof(int)*(n+1));  //申请内存空间
        for(i=0;i<n;i++)p[i]=rand()%(m-20)+2;  //产生随机的源数据集合
        p[n]=0;
        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,m);
                if(l==1)break;  //已经得到一组最优解，跳出循环输出最优解
            }
            m=sumarry(c);  //调整包容量，可加快执行速度，也可注释掉，但执行速度会慢些
            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]);  //显示最优子集，从源集合中分离子集
            }
            printf("---%d\n",sumarry(c));  //显示最优子集单个包装入容量
            bc++;  //包的个数递增
        }
        printf("装进%d个宝藏需要%d个包\n",sc,bc);
        free(p);free(c);free(t);  //释放内存
    }
}

2015-6-12  14：50 再最后一次优化代码，流程更明晰，做更详细注释。

[ 本帖最后由 wmf2014 于 2015-6-12 14:51 编辑 ]

王菇凉， 学点c++ stl， 写代码比较简洁