[ACM] POJ1837解题报告, 背包..

104 Replies

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

如果只问能否填满(这样看来又不能把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的, 和内存前面的写入有关吧)

代码:

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

104 thoughts on “[ACM] POJ1837解题报告, 背包..”

Leave a Reply

Your email address will not be published. Required fields are marked *