你的代码仍然不能通过“6、3、3、2、2、2、2”包容量为10的测试。
我现在的代码好像已经能达到最优了，小数据量的极端测试完全没问题，大数据量的随机系列测试已经大大优于以往（相同系列，随机算式是rand()%(m-2)+2），比如我随机的1000，1000也能达到511个包，原来需要535个包，算法的主要修改是：因为每个宝藏都必须装进袋子里，所以递归前并不需要最外层的循环，代码如下：

#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);p++;
    for(;n<s[p];p++);   //调节源数据指针，减少递归次数
    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;  //剪枝，取下一个数试
    }
    return 2;              //如果是循环完毕则返回到上一级通知剪枝，走下一条回路。
}
void main()
{
    int i,j,k,l,m,n,w,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+1;  //产生随机的源数据集合
        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;  //清除最优解集合数据
            t[0]=0;  //清除临时集合数据
            if(p[0]>mw)mw=p[0];  //第一个包=宝藏比平均容量大则调整平均容量
            l=bag(p,c,t,0,mw);  //此处直接递归，去掉原外层循环
            w=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",w);  //显示最优子集单个包装入容量
            esw+=w;
            if(w)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-17 15:43 编辑 ]

// 0/1 背包，动态规划实现（递归），5组数据测试正确，这下你可以闭嘴了吧

#define CAP 8
vector<int> items = {4, 3, 3, 2, 2, 2, 2}; // {2, 2, 2, 2, 2, 7, 7, 7, 7, 7}; // {6, 9, 4, 10, 9, 1}; //; {5, 4, 3, 2, 2, 2, 2}; // {3, 4, 6, 3, 7, 9, 45, 2, 10};
vector<bool> isSelect(7);
vector<int> maxKnown(CAP+1);
vector<int> itemKnown(CAP+1);

int knap(int cap)
{
    int i, space, max, maxi, t;
    
    if (maxKnown[cap])
    {
        return maxKnown[cap];
    }
    
    for (i = 0, max = 0, maxi = -1; i < items.size(); i++)
    {
        if (!isSelect[i])
        {
            isSelect[i] = true;
            
            space = cap - items[i];
            
            if (space >= 0)
            {
                t = knap(space) + items[i];
                
                if (t > max)
                {
                    max = t;
                    maxi = i;
                }
            }
            
            isSelect[i] = false;
        }
    }
    
    maxKnown[cap] = max;
    itemKnown[cap] = maxi;
    
    return max;
}

int main(void)
{
    int count = 0;
    
    while(items.size() != 0 && knap(CAP) != 0)
    {
        count++;
        int cap = CAP;
        
        vector<int> selected;
        
        while (itemKnown[cap] != -1 && cap - items[itemKnown[cap]] >= 0)
        {
            selected.push_back(items[itemKnown[cap]]);
            cap = cap - items[itemKnown[cap]];
        }
        
        for (int i = 0; i < selected.size(); i++)
        {
            for (int j = 0; j < items.size(); j++)
            {
                if (selected[i] == items[j])
                {
                    items.erase(items.begin() + j);
                    break;
                }
            }
        }
    }
    
    printf("count = %d", count);
    
    return 0;
}

小朋友，回去好好学习，表天天跟着我后面瞎起哄，要不然你这辈子真看不懂我上面这段代码

bag函数并没有选出最接近w容量的组合（ {//递归获取最接近袋子容量的组合，s数据源,c存放最接近包容量的数据,t递归得到的所有组合,w包容量）
数据 7 7 7 7 7 3 3 3 1
袋子容量 C = 10
按算法： sw = 45, m = 45/10 = 5, mw = 45/5 = 9
第一次调用时 bag(p, c, t, 0, 9) 选出的是  7， 1 没有选最接近9的 3 3 3  但是如果选了3,3,3就不会得出这个测试的最优解了

先看到这，上午工作就算打酱油了。。。（orz）
我的那个代码，已经没救了。代码把重量较小的宝箱尽可能地交换到了第1个袋子，以期望能让第一个袋子中剩余容量最大，然而这并没有什么用，（目的达不到）

对这个题的两中策略疑问：1，为什么每次都先放最大的，结果会更接近最优值，但不是最优；2，每次尽量把袋子装满，也得不到最优。
测试: 5 4 3 2 2 2 2 （C=10）
方法1结果：[5 4] [3 2 2 2] [2]
方法2结果：[5 3 2] [4 2 2 2]
测试：7 7 7 7 7 2 2 2 2 2（C=10）
结果1：[7 2] [7 2] [7 2] [7 2] [7 2]
结果2： [2 2 2 2 2] [7] [7] [7] [7] [7]

6组数据测试正确，应该再没有bug了

#define CAP 10
vector<int> items = {6, 3, 3, 2, 2, 2, 2}; // {4, 3, 3, 2, 2, 2, 2}; // {2, 2, 2, 2, 2, 7, 7, 7, 7, 7}; // {6, 9, 4, 10, 9, 1}; //; {5, 4, 3, 2, 2, 2, 2}; // {3, 4, 6, 3, 7, 9, 45, 2, 10};
vector<bool> isSelect(7);
vector<int> maxKnown(CAP+1);
vector<int> itemKnown(CAP+1);

int knap(int cap)
{
    int i, space, max, maxi, t;
    
    if (maxKnown[cap])
    {
        return maxKnown[cap];
    }
    
    for (i = 0, max = 0, maxi = -1; i < items.size(); i++)
    {
        if (!isSelect[i])
        {
            isSelect[i] = true;
            
            space = cap - items[i];
            
            if (space >= 0)
            {
                t = knap(space) + items[i];
                
                if (t > max)
                {
                    max = t;
                    maxi = i;
                }
            }
            
            isSelect[i] = false;
        }
    }
    
    maxKnown[cap] = max;
    itemKnown[cap] = maxi;
    
    return max;
}

int main(void)
{
    int count = 0;
    
    while(items.size() != 0 && knap(CAP) != 0)
    {
        count++;
        int cap = CAP;
        
        vector<int> selected;
        
        while (itemKnown[cap] != -1 && cap - items[itemKnown[cap]] >= 0)
        {
            selected.push_back(items[itemKnown[cap]]);
            cap = cap - items[itemKnown[cap]];
        }
        
        for (int i = 0; i < selected.size(); i++)
        {
            for (int j = 0; j < items.size(); j++)
            {
                if (selected[i] == items[j])
                {
                    items.erase(items.begin() + j);
                    break;
                }
            }
        }
        
        isSelect.clear();
        isSelect.resize(items.size());
        maxKnown.clear();
        maxKnown.resize(CAP+1);
        itemKnown.clear();
        itemKnown.resize(CAP+1);
    }
    
    printf("count = %d", count);
    
    return 0;
}

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

你用CAP=10，测试用 2 2 2 2 2 7 7 7 7 7 试下，输出结果是6.
建议源文件加上一些include，using nmespace，这样其他人只要复制粘贴编译就可以运行了

晕哦，这题果然不能用贪心解啊，

暂时没什么好的办法了，你是怎么想的？

我现在也没什么想法。
你和wmf的代码有一个共同点，就是先找到一个组合，然后把它T出去，后面的查找与第一组无关。如果第一组不属于最优解，那就得不到最优解。关键是【确定找到的第一个组合一定是最优解中的一个组合】。
我前一次贴的代码思路是，放宝箱时，调整现有包中的宝箱（移动和交换），希望能让一个包中的剩余容量最大。但后来发现这种调整太难了。

也就是说，目前测试我的代码，给出的都是最优解了，没找到什么明显的破绽？
我代码里有一处让我总觉得有问题的。就是我递归的一种返回“return 2”，我称为剪枝，实际上这不算剪枝，应该是一种回溯，作用是让递归寻找所有组合，比如c=10，数据6 3 2 2，一旦组合到6,3后，递归的循环就结束了，这时return 2执行回溯，可以让6和3后面的数再组合，可以组合出6,2,2，显然这才是最优组合。但我怀疑，当数据为6 3 1 1时，6,1,1的组合没有6,3的组合优，而递归里的循环已到达源数据结尾，递归将不停地回溯，造成死循环（测试时就碰到过），事实上我原来加上return 3的剪整枝的返回就是为避免这一情况的，但我发现在多数情况下使用return 3的包用量大于不用该指令（如我测试1000,1000的随机系列，用return 3指令需要535个包，而不用则只需要531个包），好在我使用的浮动包平均容量解决了这一问题，到源数据结尾的组合一定是等于最优容量而执行了return 1返回。

[ 本帖最后由 wmf2014 于 2015-6-16 16:49 编辑 ]