很奇怪。你的代码没做任何性质的优化，只是从头往后把数据加进来，在大于袋子容量前输出，是最简单的一种组合形式，尽管对一些极端数据组合不到最优，却在大数据时比我的用包要少，比如在相同随机系列下：袋子容量1000，宝藏数量1000，我采用所谓浮动平均数方法，扫描所有组合取最接近浮动平均数作为最优的组合输出，需要531个包，你的只需要511个包（该随机数理论包501个，除非敲碎宝藏达到）。
看来真如beyondyf版主所说：根本没找对路啊。

心血来潮翻了翻蓝仔以前的帖子，当年也是风生水起哈。

大家继续！

以前的技术很一般，帖子都没什么技术含量
上班了也没什么时间学习算法，所以就一直没什么变化，
很多算法都不会，比如红黑树

这问题确实比0/1背包复杂，即使用0/1背包线性复杂度解决内循环，算上贪心还是n!的复杂度。
不过，等会我会给出目前最快的解决办法，也就是用0/1背包 递归动态规划 找最大值，并贪心求包的个数

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

你能再多用几个名词术语不？除了你，你还见谁用递归实现过某问题的动态规划？

修改后，主要在put_in_bag函数，算法我也没去严格证明。。但改后比之前的要好一些，多谢@wmf2014前辈指教，调式输出先不删了，已备再改

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

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

typedef struct Bag{
    Treasure * header;
    Treasure * tailer;
    int weight;
}Bag;

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

int n = 0;
int bag_capacity = 0;
Treasure *nodes = NULL; //
Bag **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;
        Bag **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;
        int total_weight = 0;
        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 = nodes[i].prev = NULL;
            total_weight += weight;
        }
        int count = total_weight % bag_capacity ? total_weight/bag_capacity + 1 : total_weight/bag_capacity;
        //printf("-----%d\n", count);
        for (int i = 0; i < count; ++i){
            Bag * p = malloc(sizeof(Bag));
            p->header = p->tailer = NULL;
            p->weight = 0;
            bags[i] = p;
            bags[i+1] = 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){
            printf("\n%d *** [%d]:", i+1, bags[i]->weight);
            Treasure *node = bags[i]->header;
            for(; node; node=node->next)printf("%3d ", node->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){
        bags[0]->weight = nodes[index].weight; //头节点的weight表示整个链的总weight
        bags[0]->header = bags[0]->tailer = nodes + index;
        return;
    }
    put_in_bag(index + 1);
    Treasure *node = &nodes[index];
    int i = 0;
    for (Bag *bag = bags[i]; bags[i]; bag = bags[++i]){
        if (bag->weight + node->weight <= bag_capacity){
            insert_to_bag(bag, node);
            break;
        }
    }
    if (!bags[i]){
        Bag *bag0 = bags[0];
        Treasure *tmp0 = bag0->tailer;
        int as = 0, ai = 0;
        while(tmp0){
            as = bag_capacity - bag0->weight;
            if (as >= node->weight){ 
                insert_to_bag(bag0, node);
                return;
            }
           // if (ai == tmp0->weight) continue;
            ai = tmp0->weight;
            //printf("\nai=%d as=%d \n", ai, as);
            int j = 1;
            for(Bag *bag = bags[j]; bags[j]; bag = bags[++j]){
                Treasure *bm, *tmp;
                int m = 0;
                bm = bag->tailer;
                for (tmp = bag->header; tmp; tmp = tmp->next){
                    if (tmp->weight >= ai){
                        bm = tmp->prev;
                        break;
                    }
                    ++m;
                }
                //printf("\nm=%d bm=%p bmw=%d\n", m, bm, bm ?bm->weight:0);
                if (m == 0 ) continue;
                int bs = bag_capacity - bag->weight;
                for (int k = 1; k <= m; ++k){
                    int bmin = 0, bmax = 0;
                    tmp = bag->header;
                    for (int p = 0; p < k; ++p){
                        bmin += tmp->weight;
                        tmp = tmp->next;
                    }
                    tmp = bm;
                    for (int p = 0; p < k; ++p){
                        bmax += tmp->weight;
                        tmp = tmp->prev;
                    }
                    //printf("\nbmin=%d, bmax=%d\n", bmin, bmax);
                    if (ai < bmin) continue;
                    if (ai > bmax) continue;
                    tmp = bag->header;
                    for (int q = 0; q < m-k+1; ++q){
                        Treasure *ttmp = tmp;
                        int bi = 0;
                        for(int p = 0; p < k; ++p){
                            bi += ttmp->weight;
                            ttmp = ttmp->next;
                        }
                        //printf(" bi=%d bs=%d ai=%d as=%d\n", bi, bs, ai, as);
                        if (bi+bs >= ai && bi <= as + ai){
                            if (tmp0->prev) tmp0->prev->next = tmp0->next;
                            else bag0->header = tmp0->next;
                            if (tmp0->next) tmp0->next->prev = tmp0->prev;
                            else bag0->tailer = tmp0->prev;
//    for(Treasure *p = bag0->header; p; p = p->next) printf("%3d ", p->weight);
  //  printf("\n-- %d \n", tmp0->weight);
                            if(tmp->prev) tmp->prev->next = ttmp;
                            else bag->header = ttmp;
                            if (ttmp) ttmp->prev = tmp->prev;
                            bag0->weight -= ai;
                            bag->weight -= bi;
    //for(Treasure *p = bag->header; p; p = p->next) printf("%3d ", p->weight);
   // printf("\nc- %d %p %d\n", tmp->weight, ttmp, ttmp ? ttmp->weight : 0);
                            insert_to_bag(bag, tmp0);
   // for(Treasure *p = bag->header; p; p = p->next) printf("%3d ", p->weight);
   // printf("\n -3");
                      //  while(getchar() != 'w');
                            for (Treasure *tp = tmp; tp != ttmp;){
                                Treasure * tp_ = tp->next; //insert之前调用
   // printf(" %p %p \n", tp, ttmp);
                                insert_to_bag(bag0, tp);
                                tp = tp_;
                            }
    //for(Treasure *p = bag->header; p; p = p->next) printf("%3d ", p->weight);
    //printf("\n -4");
                    //    while(getchar() != 'w');
                            tmp0 = NULL;
                            goto while_loop_end;//跳到while循环
                        }
                        tmp = tmp->next; //修改
                    } //for q
                }//for k
            }//for bag
while_loop_end:     tmp0 = tmp0 ? tmp0->prev : bag0->tailer;
        }//while
    }// if
    if (!bags[i]){
        Bag * bag = (Bag *)malloc(sizeof(Bag)); //头节点
        bag->header = bag->tailer = node;
        bag->weight = node->weight;
        bags[i] = bag;
        bags[i+1] = NULL;
    }
}

void insert_to_bag(Bag *bag, Treasure *treasure){
    bag->weight += treasure->weight;
    if (!bag->header){
        bag->header = bag->tailer = treasure;
        treasure->prev = treasure->next = NULL;
        return;
    }
    //printf("\n1 ");
    Treasure *p = bag->header;
    for (; p; p = p->next){
        if (treasure->weight <= p->weight){
            treasure->next = p;
            treasure->prev = p->prev;
            if (p->prev) p->prev->next = treasure;
            else bag->header = treasure;
            p->prev = treasure;
            break;
        }
    }
    if (!p){
        p = bag->tailer;
        treasure->prev = p;
        treasure->next = NULL;
        p->next = treasure;
        bag->tailer = treasure;
    }
}

下面是3个测试：1000的随机数每次结果都不一样
input num of treasures:7
input capacity of bag:10
随机宝箱重量(y/n default to 'y'):n
input weight of treasures(<= capacity of bag):5 4 3 2 2 2 2
2 2 2 2 3 4 5
1 *** [10]:  2   2   2   4
2 *** [10]:  2   3   5
press 'q' to quit, others to continue:

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:

input num of treasures:1000
input capacity of bag:1000
随机宝箱重量(y/n default to 'y'):

(省略部分)
502 *** [994]:325 334 335
503 *** [926]:299 302 325
504 *** [888]:293 297 298
505 *** [877]:292 292 293
press 'q' to quit, others to continue:


漏了一行代码> <
================………
这个算法有问题，我设想是，对m个包裹，通过交换包裹的宝物，使第一个包裹中的剩余容量最大，但是失败了，不能按上面代码那样交换。

[ 本帖最后由 rolimi 于 2015-6-15 02:54 编辑 ]

用 Python 写了关键部分，有空再翻译成 C

# 参数：大小，整理后的数据，开始搜索的位置， 结束的位置
# 参数d: [0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 1](以数据[1, 1, 9, 9, 10]为例)
def find_one(s, d, f, t):
    d_one = 0  #一部分数据
    
    if f > s:
        f = s

    while d_one < s:
        if f >= t:
            if d[f] != 0:
                d_one = f
                d[f] -= 1
                # equal: if d_one == s
                if True == find_one (s-f, d, f, 1):
                    print(d_one)
                    return True
                else:
                    d[d_one] += 1
                    f -= 1
            else:
                f -= 1
        else:
            break
                                 
    else:
        if d_one == s:
            print(d_one)
            return True
            
        else:
            print("It's impossible")
            return False

一个测试（未进行截去尾部0优化）

>>> d = [0, 0, 5, 0, 0, 0, 0, 5, 0, 0, 0]
>>> find_one(10, d, 10, 5)
>>> find_one(9, d, 9, 5)
0
2
7
True
>>> d
[0, 0, 4, 0, 0, 0, 0, 4, 0, 0, 0]

对于优先填满包非最优解的问题，采用的是先填入大物体的策略

Hello, everyone. C 代码来啦

参数说明：
    find_one：参照上面 Python
    find：大小，元素，元素个数

#include "stdlib.h"
#include "stdio.h"

#define True_find_one -1
#define False_find_one -2

int find_one (unsigned int s, unsigned int* d, unsigned int f, unsigned int t);
int find (unsigned int s, unsigned int* d, unsigned int n);

int main (void) 
{
    unsigned int d[] = {2, 2, 2, 2, 2, 7, 7, 7, 7, 7,};

    find (10, d, 10);
        
    return 0;
}  

int find_one (unsigned int s, unsigned int* d, unsigned int f, unsigned int t)
{
    int d_one = 0;
    
    if (f > s)
    {
        f = s;
    }

    while (1)
    {
        if (d_one < s)
        {
            if (f >= t)
            {
                if (d[f] != 0)
                {
                    d_one = f;
                    d[f]--;

                    if (True_find_one == find_one (s-f, d, f, 1))
                    {
                        printf ("%d ", d_one);     //...
                        return True_find_one;
                    }
                    else
                    {
                        d[d_one]++;
                        f--;
                    }
                }
                else
                {
                    f--;
                }
            }
            else
            {
                break;
            }
        }
        else
        {
            if (d_one == s)
            {
                printf ("%d ", d_one);     //...
                return True_find_one;
            }
            else
            {
                printf ("It's impossible");     //...
                return False_find_one;
            }
        }
    }

    return False_find_one;
}
                
int find (unsigned int s, unsigned int* d, unsigned int n)
{
    unsigned int* myd = calloc (s+1, sizeof (int));
    unsigned int i;

    for (i=0; i<n; i++)
    {
        myd[d[i]]++;
    }

    for (i=s; i>=s/2; i--)
    {
        if (True_find_one == find_one (i, myd, s, s/2))
        {
            printf ("\n");    //...
            i++;
            continue;
        }
    }
    for (i=s; i>=1; i--)
    {
        if (True_find_one == find_one (i, myd, s/2, 1))
        {
            printf ("\n");     //...
            i++;
            continue;
        }
    }

    free (myd);
    return 0;
}

输入格式什么的没搞，懒...

[ 本帖最后由 pycansi 于 2015-6-15 20:52 编辑 ]

你试运行了没有？我的vc6运行你的代码是不断往上翻动的“0 10”字符。

不好意思，在 Pelles C一直没出事，疏忽了....
malloc分配的忘清0了，我改下，稍等...