注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

POJ1014 Dividing  

2009-05-14 19:48:11|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Dividing
Time Limit: 1000MS  Memory Limit: 10000K
Total Submissions: 21816  Accepted: 5246

Description

Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if all the marbles had the same value, because then they could just split the collection in half. But unfortunately, some of the marbles are larger, or more beautiful than others. So, Marsha and Bill start by assigning a value, a natural number between one and six, to each marble. Now they want to divide the marbles so that each of them gets the same total value. Unfortunately, they realize that it might be impossible to divide the marbles in this way (even if the total value of all marbles is even). For example, if there are one marble of value 1, one of value 3 and two of value 4, then they cannot be split into sets of equal value. So, they ask you to write a program that checks whether there is a fair partition of the marbles.
Input

Each line in the input file describes one collection of marbles to be divided. The lines contain six non-negative integers n1 , . . . , n6 , where ni is the number of marbles of value i. So, the example from above would be described by the input-line "1 0 1 2 0 0". The maximum total number of marbles will be 20000.
The last line of the input file will be "0 0 0 0 0 0"; do not process this line.
Output

For each collection, output "Collection #k:", where k is the number of the test case, and then either "Can be divided." or "Can't be divided.".
Output a blank line after each test case.
Sample Input

1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0
Sample Output

Collection #1:
Can't be divided.

Collection #2:
Can be divided.
Source

Mid-Central European Regional Contest 1999

 

题目大意:有一堆大理石,它们的价值从1~6不等,求是否可以将这些大理石平分成价值相等的两部分。

主要思想:

1.这道题目可以转换为是否能在给定的所有价值中找到几个价值的和为总价值的一半。由于不能破坏大理石,所以如果大理石的总价值为奇数的话,一定不能均分。

2.首先想到的是从第一个大理石开始,通过递归的方法,用总价值的一半total不断的减去各各价值,如果在求的过程中下一个价值value大于total就返回false,如果相等就返回true,否则就将total减去value后继续在后面的数组中遍历。由于递归存在很多重复的计算,所以这个程序不管怎么剪枝都都超时了。

3.这时候我们可以想到重复大量的计算加上递归子问题的性质,我们可以采用动态规划的方法。如果可以从这堆大理石中分出价值和为i的一堆大理石,那么再加上或减去其中价值为j的大理石,也是一定可以分出来的。这样的话,我们可以保存opt[i],如果opt[i]==true表示价值和为i的一堆大理石是可以分出来的,显然根据上述的定义初始化opt[0]=true。之后遍历价值为1~6的所有大理石,如果opt[j]==true,则更新opt[j+k*i]=true。其中i为当前遍历的价值为i的大理石,k表示为价值为i的大理石中的第k块。

代码如下:

#include<iostream>
#include<stdio.h>
#define MAX 60010
using namespace std;
bool canBeDiv(int value[],int sum);  //判断是否可分
bool opt[MAX];
int main(){
    int count=1,i;
    int value[7],total;
    while(true){
        total=0;
        for(i=1;i<7;i++){
            scanf("%d",&value[i]);
            total+=i*value[i];
        }
        if(!total)break;    //如果总价值为0,一定是结束的标志
        if(total&1){        //如果总价值为奇数,则一定不可分
            printf("Collection #%d:\n",count);
            printf("Can't be divided.\n\n");
            count++;
        }
        else{
            total>>=1;       //将total更新为总价值的一半
            for(i=0;i<MAX;i++)opt[i]=false;
            if(canBeDiv(value,total)){
                printf("Collection #%d:\n",count);
                printf("Can be divided.\n\n");
            }
            else{
                printf("Collection #%d:\n",count);
                printf("Can't be divided.\n\n");
            }
            count++;
        }
    }
    return 0;
}
bool canBeDiv(int value[],int sum){
    int i,j,k;
    int max,tmp;
    opt[0]=true;    //初始化
    max=0;          //max表示当前所能分出的最大的价值和
    for(i=1;i<7;i++){
        if(!value[i])continue;   //跳过个数为0的大理石
        for(j=max;j>=0;j--){
            if(opt[j]){      //如果价值和为j的大理石堆是可以分出来的
                for(k=1;k<=value[i];k++){ 
                    tmp=j+k*i;

                    if(tmp>sum||opt[tmp])break;//如果价值和大于sum或是opt[tmp]已经更新过,则不对其处理
                    if(tmp==sum)return true;
                    opt[tmp]=true;

                    //if(max<tmp)max=tmp;这句去掉了,并改成了下面红色的部分
                }
            }
        }

        max+=i*value[i];
        if(max>sum)max=sum;
   //价值和大于sum的部分不需要管
    }
    return false;
}

后记:

1.原本对动态规划就不是很了解,最后不得去查找解题思路,这里要感谢http://www.cppblog.com/AClayton/archive/2007/09/14/32185.html的朋友,写的很详细。

2.之前的代码本来是自己借鉴别人的思想写的,交了后用了700多ms,回头再和别人的代码对照了一下,有两处有点差异,改过后就是上面的代码了,以0ms过。上面红色的部分就是变动的部分。小小的细节就能有这么大的差异,值得思考。

3.这里有一个问题,就是opt[tmp]==true时(代码中红色的部分)是否要退出循环。有人提问说如果opt[tmp],即opt[j+k*i]就算被处理过,opt[j+(k+...)*i]也不一定处理过,所以不应该退出循环。但是我们这样看,程序的处理实际上是遍历大理石堆中的每一个大理石,并把它们价值加到之前已经处理过的大理石上,即处理完opt[tmp]后,再处理opt[tmp+x],如果真的发生了如上述的假设所说的opt[tmp+x]未被处理过,那么因为for(j=max;j>=0;j--)这个循环是从后往前处理的,opt[tmp]被处理的时间只有一种可能,就是在当前假设之前就被处理了。显然在当前的假设下tmp==j+k*i>j,所以j==tmp在for(j=max;j>=0;j--)循环中一定在之前被访问到,那么之前这个得到的tmp会不会加上这个变动的x呢?x是通过for(k=1;k<=value[i];k++)这个循环得到的,其实就是每次增加一个价值为i(也就是之前假设的x)的大理石,这两个循环的嵌套是怎么工作的应该不用多说了,根据嵌套for循环可以看出,如果说opt[tmp]被处理过的话,那么opt[tmp+x]肯定在之前就被处理过了,这与假设不符,所以上面的if语句是正确的。

  评论这张
 
阅读(457)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017