[ACM] POJ1014解题报告

99 Replies

题目:
6种球, 价值分别为1..6, 给出每种的数量, 问能不能分成价值相同的两堆

思路:
1. 将它当成背包问题来看, 包的容积一定(这里的”体积”就是球的价值, 包的容积V=球总价值的一半), 问能不能分成相等两堆即, 包是不是能装满.
2. 这里不用球背包问题中的极值, 不存在价值的概念, 所以v数组用bool型就可以.
3. 因为每种球数量有限制所以不是典型的完全背包问题(目前就看了两个..01背包和完全背包), 我对v中的每一个true它后面每i个赋值成为true, 直到这层的球耗尽. 比如开始v[0]=true v[1..V]=false, 1球的数量为10, 则第一层i循环后, v[0..10]=true v[11.V]=false
4. 3中直接赋值会对后面的计算有影响, 我很蹩脚的另外建了个列表作临时用…
5. 一次AC, 但是时间效率很低, 7XXms..都快超了(大家都爱说..都快超了), 感觉应该是算法过于繁琐..还倒来倒去的, 有空得试试O(log V/c[i])那算法
6. <背包九讲>下载 http://axlarts.com/uploads/documents/pack9lessons.doc 没作者 没写版权声明 直接转了..

代码:
[cpp] #include <cstdio>
#include <cstring>

int main() {
int n[7],N,V;
bool v[60001],t[60001];
N=0;
while(++N) {
V=0;
bool isEnd=true;
for(int i=1;i<=6;i++) {
scanf("%d",n+i);
V+=n[i]*i;
if(n[i])
isEnd=false;
}
if(isEnd)
break;

printf("Collection #%d:\n",N);
if(V%2) {
printf("Can’t be divided.\n\n");
continue;
}

///initialize
V/=2;
v[0]=true;
memset(v+1,false,V);

for(int i=1;i<=6;i++) {
memset(t,false,V+1);
for(int j=0;j<=V;j++) {
if(!v[j])
continue;
for(int k=0;k<=n[i]*i;k+=i) {
if((j+k)>V)
break;
t[j+k]=true;
}
}
for(int j=1;j<=V;j++)
v[j]=t[j];
}

if(v[V])
printf("Can be divided.\n\n");
else
printf("Can’t be divided.\n\n");
}
return 0;
}[/cpp]

99 thoughts on “[ACM] POJ1014解题报告”

Leave a Reply

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