以下是引用wujieru在2011-1-1 14:33:05的发言：

背包问题 贪心算法

以下是引用sunyh1999在2011-1-2 12:21:47的发言：

背包....

以下是引用StarWing83在2011-1-2 12:59:38的发言：

#include  
#include  
#include  
 
int main(void)
{
    struct  
    {
        char *name;
        int size;
        int value;
    } item[] =  
    {
        {"A", 3, 4},
        {"B", 4, 5},
        {"C", 7, 10},
        {"D", 8, 11},
        {"E", 9, 13},
    };
#define ILEN (sizeof(item)/sizeof(item[0]))
#define PSIZE 17
 
    int max;
    {
        int i, j, v[PSIZE + 1] = {};
 
        for (i = 0; i < ILEN; ++i)
            for (j = item.size; j <= PSIZE; ++j)
                if (v[j] < v[j-item.size] + item.value)
                    v[j] = v[j-item.size] + item.value;
        printf("%d\n", max = v[PSIZE]);
    }
 
    {
        int i, j, v[PSIZE + 1] = {}, s[PSIZE + 1] = {};
 
        for (i = 0; i < ILEN; ++i)
            for (j = item.size; j <= PSIZE; ++j)
                if (v[j] <= v[j-item.size] + item.value)
                {
                    v[j] = v[j-item.size] + item.value;
                    memcpy(s[j], s[j-item.size], sizeof(s[j]));
                    ++s[j];
 
                    if (j == PSIZE && v[j] == max)
                    {
                        int i, j;
                        for (i = 0; i < ILEN; ++i)
                            for (j = 0; j < s[PSIZE]; ++j)
                                printf("%s", item.name);
                        printf("\n");
                    }
                }
    }
 
    return 0;
}

以下是引用sunyh1999在2011-1-3 17:23:01的发言：

我发的是01包

以下是引用StarWing83在2011-1-3 21:05:00的发言：

楼上想说明有公式么？据说背包问题不是P问题哦……另外，这里的解法涉及到了复数的集合运算。估计比一元二次方程要复杂好几个数量级呢，要算出来估计得靠matlab

以下是引用pangding在2011-1-4 19:44:49的发言：

收藏一下这个帖子吧，有机会研究研究。