学步园

Poj_1014 & Zoj_1149 (Dividing) 解题报告

一．问题描述：

有价值分别为1..6的大理石各a[1..6]块，现要将它们分成两部分，使得两部分价值之和相等，问是否可以实现。其中大理石的总数不超过20000。

二．问题分析：

很明显是一个划分问题---分成等价值的两部分，进一步可以发现也是一个组合问题，即：第一部分选择哪些大理石，选择多少；第二部分则选择剩余即可。

首先，排除总价值之和为奇数的情况，输出“Can't be divided.”

然后对于组合最优化问题，动态规划无疑是最强有力的方法，而且这个问题似乎与经典的背包问题有点类似，不过这里是两个背包，而且要求的是“判断两者是否可以装等价值的物品”，比起要你求出如何装载成等同价值的两个背包，难度减少了不少，所以即使这里涉及到的是两个背包，也可以方便的用动态规划。

三．第一个动态规划算法设计：

使用传统的二维数组，与背包问题类似，用f[i][j] 表示：可否从1 到 i的大理石中选出部分大理石，使得其价值之和等于j，若能则置f[i][j]为 true,不能就置为 false。因此最后需要判断的就是：如果有一个i满足f[i][mid] == true 则可以实现题目要求，否则不可以实现。下面给出DP的边条与状态转移方程：

首先边界状态：f[i][0] = false； 0<=i<=6（即肯定可以选出价值和等于0的)

其次状态转移方程：

f[i][j] = f[i][j] or f[i-1][j-i*k];  1<=i<=6；1<=j<=sum/2； k表示从第i价值的大理石中任意选取0~a[i]项，即 0 <= k <= a[i]。 (sum表示输入的总价值)

伪代码如下：  

1. 计算总价值sum，sum为奇数直接输出，并重新开始读入

2. mid = sum /2；                //只要一半

3. Set all f[i][j] = false；

4. for ( i = 0; I <= 7; i++ ) f[i][0] = true；

5. for ( I = 1; I <= 6; i++ )

6.     for ( j = 1; j <= mid; j++ )

7.         for ( k = 0; k <= a[i]; k++ ) {

8.             如果 j-i*k < 0 break；

9.             如果f[i-1][j-i*k]为真{设置f[i][j]为真；break；}

10.        }

11.i 从1到6，检查f[i][mid]是否有 true 值。输出相应即可

看起来挺简单的一个转移方程，设计起来也很容易，弄好了之后兴匆匆的提交：TLE! 没可能啊，再提交一把，仍然TLE！！ 郁闷，分析一下发现，给出大理石总数可以到20000，那么假设a[6] = 20000，那么k需要搜索到20000，j更需要搜索到20000*6/2 = 60000，也即这个形式上的O(18*N*N)复杂度的算法并不是一个真正的多项式算法(N不是i，只有6)，而实质是一个指数时间复杂度的伪多项式算法（其实背包问题的动态规划也是如此的），它不是与输入的物体数目相关，而是与它的重量什么的相关，而这个重量确实可以到无限大，当然这里的物体指“6堆”，重量指“每堆的数量”了。因此本算法TLE是不难想象的。

四．双向动态规划算法设计：

无法解决，就只好上网搜索该题的解决之道了，其中一个高手的文章提到了使用双向DP来解决Zoj 1149（即本题）的方法，简要的描述如下：

实践发现：本题在i较小时，由于可选取的大理石的价值品种单一，数量也较少，因此值为true的状态也较少，但随着i的增大，大理石价值品种和数量的增多，值为true的状态也急剧增多，使得规划过程的速度减慢，影响了算法的时间效率。

另一方面，我们注意到我们关心的仅是能否得到价值和为mid的值为true的状态，那么，我们能否从两个方向分别进行规划，分别求出从价值为1..3的大理石中选出部分大理石所能获得的所有价值和，和从价值为4..6的大理石中选出部分大理石所能获得的所有价值和。最后通过判断两者中是否存在和为mid的价值和，由此，可以得出问题的解。

状态转移方程可以改进为：

当i <= 3时：

f[i][j]=f[i][j]  OR  f[i-1][j-i*k]           (0<=k<=a[i])

当i > 3时：

f[i][j]=f[i][j]  OR  f[i+1][j-i*k]          (0<=k<=a[i])

规划的边界条件仍然为：f[i][0]=true； 0<=i<=7

这样，若存在k，使得f[3][k] = true并且 f[4][Mid-k] = true，则可以实现题目要求，否则无法实现。

实际上最后的这个判断是容易理解的，因为选择嘛，只能从这6堆大理石中选择，所以f[3][x]如果为真，表示可以从前3堆中选取价值为x；而同时f[4][mid-x]如果为真，表示可以从后面3对选取价值为Mid-x。那么就可以从这6堆中选取共Mid价值的大理石，从而形成一堆，而剩余的成为另外一堆。因此最后只要检查是否存在i：f[3][i] = true && f[4][mid-i] 即可。

根据这个双向DP，就只要改变一些上面的单向DP伪代码就可以了：