_HDU 1059 Dividing 分配（AC代码）多重背包的变形_台圣宝轧花网
题意：两个人共同收藏了一些石头，现在要分道扬镳，得分资产了，石头具有不同的收藏价值，分别为1、2、3、4、5、6共6个价钱。问：是否能公平分配？
输入：每行为一个测试例子，每行包括6个数字，分别对应6种价钱的石头数目，比如101200代表价值为1的石头有1个，价值为2的石头有0个....价值为4的石头有2个。他们具有的石头数量的上限为2万个。
输出：见题目吧。
思路：想用多重背包的方式解决，也想转01背包比较简单。直接转01背包会超时，得想办法。可以用多重背包的方法，用二进制来减少复杂度，应该可行。我用的是偷懒的办法，将数据都减小，比如某个价值的石头有1千个，是偶数，那就可以直接分掉，每人500啦，但是可能会有奇数个的情况，所以不能单独将某价值的石头一次性分完。那么留多少合适？我觉得留4合适，但是实际上留了8个以下才能AC。
出现下面情况说明了不能将某个价值的石头总数mod2：
价值：1 2 3 4 5 6
数量：1 0 8 0 1 0
解释：假如%2的话，价值为3的石头就变为0个，剩下两个石头，价值分别为1和5，分不了！
所以余数必须大于2，测试了一下，6不行，8以上的偶数就行了。
现在，数据的大小降下来了，转成01背包就简单多了。将剩下的所有石头的的价值的一半假设为背包的容量，将石头的体积设为等价于其价值大小。什么意思呢？
举个例子：
价值：1 2 3 4 5 6
数量：1 0 2 0 1 0
体积：1 2 3 4 5 6
假设这是数值大小降低后的结果，一眼可以看出1+5=3*2，可以公平分配，所有石头的总价值为12，假设其中一个人是我，那么我必须分配到价值为6的石头才是公平的，不用管到底分得1块还是2块石头。而其价值与体积已经假设是相等的，那么设我的背包大小为6，我想从这些石头（4块）中挑出一些石头，使我的背包装满，只要能刚好装满，证明能公平分配，即dp[x]=x。 这个可列举一些小的数据后计算就能验证。
Read full article from _HDU 1059 Dividing 分配（AC代码）多重背包的变形_台圣宝轧花网
No comments:
Post a Comment