成为酱油面的决心

求严格背包, 这次要求是所有物品都必须使用, 问有多少种填满的方法(具体看题)

如果只问能否填满(这样看来又不能把v=重量*杠杆长度看成物品了, 不是传统背包..好难归纳) 那只要用bool型数组记录, 因为不能不用 所以用两个数组更替(a0[i]==true doesn’t mean a1[i]==true, so.)

问有多少种方法把bool换成计数器即可

2010/08/05 Update:
在”能不能放满”(或者填满特定容量) 这种题型中, 以下三种情况是可以让我们求”符合要求的组合有多少种”
1. 一个物品具有多种可选的体积. 比如在本题中是”在物品体积可变, 并且能够为负的情况下, 能不能使占用空间恰为0(平衡)”
2. 物品可以选择不用
3. 1&&2
原因很简单, 上面三种情况的补集是”物品体积固定并且必须全用”, 这种情况最后占用的容积是常数, 逆否命题即上面的蓝字部分成立.

细节:
int *a=(int *)malloc(sizeof(int)*20001);  //sizeof(a)==4
int a[20001];  //sizeof(a)==80004;
混淆了一下 导致数组不能初始化, 结果是诡异的3 (答案是2)
debug的时候数组里是非常混乱的 (比如a0[9999]==-265219901)
但是release的时候数组即使不初始化也都为0, 但不一定(诡异的3就是因为某个数==1, 应该初始化为0的, 和内存前面的写入有关吧)

代码:

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

int main() {
    int *a0,*a1;
    int C,G,c[20],g[20];

    a0=(int *)malloc(sizeof(int)*20001);
    memset(a0,0x00,sizeof(int)*20001);
    a0[10000]=1;
    scanf("%d%d",&C,&G);
    for(int i=0;i<C;i++)
        scanf("%d",c+i);
    for(int i=0;i<G;i++)
        scanf("%d",g+i);

    int v;
    for(int i=0;i<G;i++) {
        a1=(int *)malloc(sizeof(int)*20001);
        memset(a1,0x00,sizeof(int)*20001);

        /*/debug
        for(int k=9900;k<=10100;k++)
            if(a0[k])
                printf("a0[%d]=%d, ",k,a0[k]);
        printf("\n");//*/

        for(int j=0;j<C;j++) {
            v=g[i]*c[j];
            for(int i=19000;i>=1000;i--)        //order doesn't make sense.
                a1[i+v]+=a0[i];

            /*/debug
            for(int k=9900;k<=10100;k++)
                if(a1[k])
                    printf("a1[%d]=%d, ",k,a1[k]);
            printf("\n");//*/

        }
        free(a0);
        a0=a1;
    }

    printf("%d\n",a0[10000]);

    return 0;
}