[ACM] POJ2184解题报告

晚上真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…)

[cpp]
#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;
}
[/cpp]

Asher.GG

git gut together

[ACM] POJ2184解题报告

110 thoughts on “[ACM] POJ2184解题报告”

Leave a Reply Cancel reply