[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解题报告”

  1. Java

    准备留在灵异事件下面..因为今天带电脑也出了这个问题..一听耳熟,是以前练街舞的曲子..不知道什么程序再放..然后听写歌词把它goo出来了..HO..(我去刷新..)

    Reply ↓
  2. Java

    没说完…留在这下面是因为这里留的人少..平均分配资源..感觉你所有的日志都有人留言..牛鞭..

    Reply ↓
  7. ljq444587868

    #include
    #include
    int shuzu[7];
    int f(int n,int sum)
    {
    int s=0,i=0,t=0;
    if(!sum)
    return 1;
    if(!n)
    if(sum)
    return 0;
    for(i=0;isum)
    break;
    if(s>sum)
    s-=n;
    for(i=s/n;i>=0;i–)
    for(t=1;t=sum-i*n)
    if(f(n-1,sum-i*n))
    return 1;
    return 0;
    }
    void main(void)
    {
    int num=0,h=0,n=0;
    while(1)
    { n=0;
    memset(shuzu,0,sizeof(int)*7);
    for(h=1;h<=6;n+=shuzu[h]*h,h++)
    scanf("%d",shuzu+h);
    if(!n)
    break;
    if(n%2)
    printf("Collection #%d:\nCan't be divided.\n\n",++num);
    else if(f(6,n/2))
    printf("Collection #%d:\nCan be divided.\n\n",++num);
    else
    printf("Collection #%d:\nCan't be divided.\n\n",++num);
    }
    }

    Reply ↓

Leave a Reply

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