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

如果只问能否填满(这样看来又不能把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;
}

晚上真happy, ac了前天开始的题,还写了点东西..好久没写东西了啊 ^_<

最近做了几道背包(好像就两道吧..),自己总结一下

(为什么我突然觉得这种假装有人会看我写的东西的语气很诡异..显然很诡异啊, 赶快找点人来看..)

目前就做过01背包 完全背包 和多重背包吧.
严格的背包, 可以根据背包九讲上把除了v(1)到v(N)全附成0x80000000(负无穷), 然后按照不严格背包的思路DP
这种情况下, 如果对每一层优化, 就是最后一层只算v[V], 倒2层只从v[V-vn]..V[V]那样的优化, 这样如果严格背包得不到结果, 那就不知道不严格背包的结果了, 虽然也确实没要求..
做非严格背包也可以用严格背包的方法, 从最后的v[]数组中选出最大的即可, 但是这样不能使用每层的优化

然后像http://poj.grids.cn/problem/1276/discuss/这样不求价值只求空间占用的题目, 显然是用严格背包(不然求毛啊), 因为不用存储价值量, v[]用bool型即可, 和上面思路一样, 只是负无穷是false, 非负无穷(这个体积大小可以做到被完全占用)是true

http://poj.grids.cn/problem/2184/status/ 这个开始用的二维背包..傻逼了. 后来发现只要把s看成体积, f看成价值即可. 替换的时候比较体积和价值的和. 因为要求的东西和体积\价值有直接联系, 思维上转换一下就行

错了一天的原因是s可能是负的!! 太阴险了, 01背包刷新v[]的时候是从后像前, 否则就是完全背包. 但是如果某个物品体积是负的, 从后向前刷新v[]前面刷新过的的就会影响接下来的比较..

代码: (用个数组记录非负无穷的数组元素就能0ms吧 懒得折腾了 复杂度O(2*10^7)无压力AC…)

#include <stdio.h>
#include <stdlib.h>
#define orz 200001

int main() {
	int N,s[100],f[100];
	int a[orz];
	int k,result;

	scanf("%d",&N);
	for(int i=0;i<N;i++)
		scanf("%d%d",s+i,f+i);

	for(int i=0;i<orz;i++)
		a[i]=(int)-2e9;
	a[(orz/2)]=0;

	for(int i=0;i<N;i++) {
	    if(s[i]>0) {
            for(int j=orz-1-s[i];j>=0;j--)
                if(a[j]!=(int)-2e9 && a[j+s[i]]<a[j]+f[i])
                    a[j+s[i]]=a[j]+f[i];
	    }
        else {
            for(int j=-s[i];j<=orz-1;j++)
                if(a[j]!=(int)-2e9 && a[j+s[i]]<a[j]+f[i])
                    a[j+s[i]]=a[j]+f[i];
        }
	}

    result=(int)-2e9;
    for(int i=(orz/2);i<orz;i++) {
        if(a[i]<0)
            continue;
        result=a[i]+i>result?a[i]+i:result;
    }
	printf("%d\n",result-(orz/2));

	return 0;
}