题目:
6种球, 价值分别为1..6, 给出每种的数量, 问能不能分成价值相同的两堆

思路:
1. 将它当成背包问题来看, 包的容积一定(这里的”体积”就是球的价值, 包的容积V=球总价值的一半), 问能不能分成相等两堆即, 包是不是能装满.
2. 这里不用球背包问题中的极值, 不存在价值的概念, 所以v数组用bool型就可以.
3. 因为每种球数量有限制所以不是典型的完全背包问题(目前就看了两个..01背包和完全背包), 我对v中的每一个true它后面每i个赋值成为true, 直到这层的球耗尽. 比如开始v[0]=true v[1..V]=false, 1球的数量为10, 则第一层i循环后, v[0..10]=true v[11.V]=false
4. 3中直接赋值会对后面的计算有影响, 我很蹩脚的另外建了个列表作临时用…
5. 一次AC, 但是时间效率很低, 7XXms..都快超了(大家都爱说..都快超了), 感觉应该是算法过于繁琐..还倒来倒去的, 有空得试试O(log V/c[i])那算法
6. <背包九讲>下载 http://axlarts.com/uploads/documents/pack9lessons.doc 没作者 没写版权声明 直接转了..

代码:

 #include <cstdio>
 #include <cstring>

 int main() {
    int n[7],N,V;
    bool v[60001],t[60001];
    N=0;
    while(++N) {
        V=0;
        bool isEnd=true;
        for(int i=1;i<=6;i++) {
            scanf("%d",n+i);
            V+=n[i]*i;
            if(n[i])
                isEnd=false;
        }
        if(isEnd)
            break;

        printf("Collection #%d:\n",N);
        if(V%2) {
            printf("Can't be divided.\n\n");
            continue;
        }

        ///initialize
        V/=2;
        v[0]=true;
        memset(v+1,false,V);

        for(int i=1;i<=6;i++) {
            memset(t,false,V+1);
            for(int j=0;j<=V;j++) {
                if(!v[j])
                    continue;
                for(int k=0;k<=n[i]*i;k+=i) {
                    if((j+k)>V)
                        break;
                    t[j+k]=true;
                }
            }
            for(int j=1;j<=V;j++)
                v[j]=t[j];
        }

        if(v[V])
            printf("Can be divided.\n\n");
        else
            printf("Can't be divided.\n\n");
    }
    return 0;
 }