POJ1014解题

POJ的1014是一题挺有意思的搜索题。题目说有价值为1到6的石头若干,然后每次的数据分别给出它们的数量,要求求出这些石头是否能按价值平均分。比如价值1的石头两块,价值2的石头1块,那么可以平均分。也有很多情况不能平均分。

所以思路就是搜索吧。当然如果总价值本身就是奇数,那么肯定不可以平均分了。但是总价值是偶数,也不一定能平均分。所以就搜索一下这些石头能否刚好凑到总价值的一半,如果可以就能够平均分了,否则不行。

但是题目的规模是每种石头的数量是0到20000,其实大家都知道直接搜索肯定会超时。然后对于这道特殊的题,剪枝的方法更是多种多样。但是我一直想不改进搜索,而是找到小规模的等价问题,从而求解。比如六种价值的石头数量“2,4,0,0,0,0”。那么两边都有一块价值为1的石头,两边都有两块价值为2的石头,刚好完全平分价值。因为我们给出的一组数据有解,而且解的两边有相同的东西,所以容易想到,两边各去掉一块1或各去掉一块2,两边还是相等的,所以可以知道,如果给出一组数据是“0,4,0,0,0,0”还是有解的。

也就是说,我想把可能规模很大的数据化为等价的规模很小的数据,直接搜索求解。但是说得容易,却很难证明其正确性,直到看到网上的一篇分析才知道。但是那篇分析不够严谨和清楚,我严谨地证明一次。

首先,如果原数据无解(不可平分),那么任何一种石头的数量减去2之后,仍然是无解。可以反证,假设减去2后的数据有解,也就是可以等分为两堆,那么每边各添加那种减去的石头一块,那两堆的价值还是相等,就跟原数据不可分矛盾了,因此得证。

然后,如果原数据有解,其中一种石头减去2之后,可能有解,也可能无解,我们很容易就可以举出例子,所以不举例子了。也就是这里,让我觉得很无奈,因为失去等价性,这种方法就没有意义了。但是后来发现,原来在某个数量上而且原数据有解,是可以肯定地得到减2之后也有解的,从而可以找到最小规模的等价数据。下面就介绍。

所以我们现在是假设原数据有解,以价值为6的石头说明问题吧。假设本身原数据的其中一个解,是两边都有6的,那么价值6的石头减2的数据肯定有解。然后如果其中一个解是6全在一边,如果能够把其中一些6交换到右边,那么就是刚才的情况了。然后我们会发现,有时候一定能够交换过去。比如,如果右边有六个5或以上,那么肯定可以把左边的五个6交换过去,因此如果右边有六个5或以上,把6的石头减2也还有解。同理,三个4,两个3,三个2,六个1或以上,都可以使得6从左边交换到右边。然后怎样才能使得右边会至少出现五个6等等呢,要不出现的话,右边最大是5*5 + 4*2 + 3*1 + 2*2 + 1*5 = 45。所以只要左边只要有8个6,那么肯定可以交换过去。

因此,结论是如果价值为6的个数大于8,都能把个数减2,而可分与否的性质和原来不变。因此6的个数如果大于8,偶数的可以等价为6,奇数的个数等价为7。同理,其他价值的石头也有类似的性质,规模减少后就可以直接搜索了。

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s