晚上真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;
}