PKU POJ 1014 Dividing

PKU POJ 1014 Dividing

发表时间:2007年9月2日 18时7分17秒        评论/阅读(2/11)
这道题的分类竟然在“简单”里面…… 
确实没有找到比较简单的方法 

动态规划: 

 1#include<stdio.h> 
 2bool opt[60000]; 
 3int num=0
 4int mid,max; 
 5int stone[7]; 
 6int input() 
 7
 8    scanf("%d%d%d%d%d%d",&stone[1],&stone[2],&stone[3],&stone[4],&stone[5],&stone[6]); 
 9    if(!stone[6]&&!stone[1]&&!stone[2]&&!stone[3]&&!stone[4]&&!stone[5]) {return 1;} //读到末行 
10    num++
11    printf("Collection #%d:\n",num); 
12    mid=0
13    for(int i=1;i<=6;i++) mid+=stone[i]*i; 
14    if (mid % 2 ==1)                                          //明显的剪枝 
15    
16        printf("Can't be divided.\n\n"); 
17        return 2
18    }
 
19    else mid/=2;                                              //我们的任务就是求opt 
20    return 0
21}
 
22
23void dp() 
24
25    memset(opt,0,60000);          //初始化,opt所有成员为false 
26    opt[0]=true;                        //opt[0]显然是true 
27    max=0;                             //当前最大值是0 
28
29    for (int i=1;i<=6;i++)           
30    
31        if (stone[i]>0
32        
33            for(int j=max;j>=0;j--)   // 从当前最大值开始往下算 
34            if (opt[j])                      //找到可行的j 
35            
36                if (opt[mid])              //判断是否已经求出结果 
37                
38                    printf("Can be divided.\n\n"); 
39                    return
40                }
 
41                for (int k=1;k<=stone[i];k++)         //在刚找到的可行j基础上加石头. 
42                
43                    if (j+k*i>mid || opt[j+k*i]) break;  //如果已经大于总价值的一半mid,或opt[j+k*i]已计算,跳出循环 
44                    opt[j+k*i]=true
45                }
 
46            }
 
47        }
 
48        max=max+i*stone[i];                           //更新当前最大值 
49        if (max>mid) max=mid;                        //如果当前最大值超过了mid,对其赋值为mid 
50    }
 
51    printf("Can't be divided.\n\n");                     //如果从1到6循环完一遍后仍然没有算出opt[mid],说明无解 
52}
 
53
54int main() 
55
56    while (1
57    
58        int t=input(); 
59        switch (t) 
60        
61            case 1 : return 0;   //读到末行,结束 
62            case 2 : continue;  //读到明显的剪枝 
63            default : dp(); 
64        }
 
65    }
 
66    return 0
67}
 



本题是找按价值均分大理石的方案是否存在,由于分配时不能破坏大理石,所以有个显而易见的剪枝:当所有的大理石的总价值为奇数时肯定不能被均分。 
把问题转化一下即:由一个人能否从原大理石堆中取出总价值为原来一半的大理石 
本题的主要算法是动态规划 
数组opt代表状态: 
设总价值为V, 
当opt[k]==true时,说明,可以有一人获得价值k,另外一人获得价值V-k的大理石分配方案。反之若opt[k]=false 说明这种分配方案不存在 
我们的任务就是计算出opt[v/2]是true还是false,即opt[mid]。 
显然有opt[0]==true的方案存在,即一个人什么都不分,另外一个人拿走全部的大理石 

设i(1<<6)为石头的价值,试想若opt[k]==true,而且在这堆总价值为k的石头中有一块石头的价值为i,那么opt[k-i]这种分配方案就是必然存在的了。反过来想,当opt[k]==true ,如果能再向k中增加一价值为i的大理石,则opt[k]==true必然成立 
石头有两个属性,一个是价值另一个是数量,这里stone[i]代表价值为i的大理石的数量,我们根据其中一个属性:价值 来划分阶段。 
即for (int i=1;i<=6;i++),opt[k]表示状态是否存在(这里的状态是指能否从原石头堆中分出价值为k的新石头堆) 
在初始阶段是i=1,初始状态是opt[0],max代表目前满足opt[k]==true这一条件的k的最大值 

for(int j=max;j>=0;j--) 
//从当前最大值opt[开始],根据前面提到的opt[j]==true成立则opt[j+i]==true亦成立的理论,在原有状态opt[j]==true已存在的条件下加入stone[i]阶段的石头,得到新的状态  


PS  :感谢重庆大学微软技术俱乐部的肖阳同学
       原来这道题果然有更简单的方法
http://www.blogjava.net/zellux/archive/2007/07/30/133416.html

posted on 2007-09-14 02:11 流牛ζ木马 阅读(4063) 评论(7)  编辑 收藏 引用

评论

# re: PKU POJ 1014 Dividing 2008-11-05 23:56 zhao

如果输入是:
2 0 0 0 0 0
结果是:
Can't be divided.

?  回复  更多评论   

# re: PKU POJ 1014 Dividing 2009-03-23 22:17 allen

您好,我是刚接触ACM的菜鸟,拜读了您的解题思想,有个问题想请教一下,就是那个状态数组最大为60000个,这个数据有什么根据吗?  回复  更多评论   

# re: PKU POJ 1014 Dividing 2009-04-17 16:53 黄河勇者

上面的提到状态数组最大为60000,是根据题意得出的,题意说最多有20000块石头,则一个人的最大价值为60000  回复  更多评论   

# re: PKU POJ 1014 Dividing 2009-04-17 20:02 黄河勇者

博主能不能将43行代码的opt[j+k*i]满足就跳出循环解释一下,小弟认为在当该条件满足时不一定要跳出循环(此处可能博主有误),因为opt[j+k*(i+1)]不一定计算出,所以循环有必要进行下去,如小弟理解有误,望博主指点。小弟的AC代码(算法思想按博主所写):http://hi.baidu.com/黄河勇者  回复  更多评论   

# re: PKU POJ 1014 Dividing 2009-08-29 15:01 lymfs

博主能不能将43行代码的opt[j+k*i]满足就跳出循环解释一下  回复  更多评论   

# re: PKU POJ 1014 Dividing 2009-12-31 11:52 CRonaldo

@zhao
这是程序的一个bug.
根据你给出的"2 0 0 0 0 0",
尽管第44行中给opt[mid]赋值true,但程序却执行不到36行了.
可以做如下更正:
36                if (opt[mid])              //判断是否已经求出结果
37                {
38                    printf("Can be divided.\n\n");
39                    return;
40                }
41                for (int k=1;k<=stone[i];k++)         //在刚找到的可行j基础上加石头.
42                {
43                    if (j+k*i>mid || opt[j+k*i]) break;  //如果已经大于总价值的一半mid,或opt[j+k*i]已计算,跳出循环
44                    opt[j+k*i]=true;
45                }
 
将上述的if语句和for循环对换.
 
@黄河勇者
@lymfs
opt[j+k*i]. 这里j初始化为max,并不断减小.
我们注意到,下一次循环中max实际上是由上一次的价值×数量(i*stone[i])累计而成;
而在累计过程中,opt相应位置不断赋值true.
刚开始j==max的时候,opt[j+k*i]显然不可能成立,
∵max是以前所有价值的和(排除max>mid的情况),
此时j+k*i显然大于max,即opt[j+k*i]从未被赋值过.
这就是说opt[j+k*i]==true成立的情况是在j不断减小的过程中发生的.
此时,分两种情况:
①j+k*i≥max.
除了opt[max],opt[j+k*i]是本次for(int j=max;j>=0;j--)循环中被赋值true,
即不存在opt[j+k*i]==true的情况.
②j+k*i<max.
可以将j+k*i看做小于max的j'.
显然j'是由max不断减小得到,j由j'不断减小得到,
opt[j]==true, opt[j']==true, j' - j == k*i.  
j''==j+(k+1)*k, opt[j'']=?
还是无法用数学证明.继续研究...还请博主指点下.
  回复  更多评论   

# re: PKU POJ 1014 Dividing 2010-08-08 01:38 444587868

Problem: 1014 User: 0809114213
Memory: 172K Time: 0MS
Language: C Result: Accepted

#include<stdio.h>
#include<string.h>
int shuzu[7];
char hehe[7][5000];
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;i<shuzu[n];i++)
if((s+=n)>sum)
break;
if(s>sum)
s-=n;
for(i=s/n;i>=0;i--)
for(t=1;t<=n-1;shuzu[0]+=shuzu[t]*t,t++)
if(shuzu[0]+(s/n-i)*n>=sum-i*n)
if(hehe[n-1][sum-i*n]!='0')
if(f(n-1,sum-i*n))
return 1;
else
hehe[n-1][sum-i*n]='0';
return 0;
}
void main(void)
{
int num=0,h=0,n=0;
while(1)
{ n=0;
memset(shuzu,0,sizeof(int)*7);
memset(hehe,'1',sizeof(char)*35000);
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);
}
}


  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年8月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

公告

MY Email/MSN :mars1021@163.com QQ : 27402040 流牛ζ木马

常用链接

留言簿(6)

随笔档案

相册

搜索

最新随笔

最新评论

阅读排行榜

评论排行榜