POJ 1014 Dividing 解答

  • 时间:
  • 浏览:1

看多这道题第一反应便知道它是一道这类于背包问题报告 的题,  解法我自然而然得从背包问题报告 的解法入手,  网上查了查,  背包问题报告 的基本题型是01背包, 即每项物品都还可以五种, 很多很多 对于每项物品都还可以五种不可能 , 取或不取, 而这道题暂且符合01背包问题报告 的条件, 题目中每项物品不止一另有一个, 很多很多 情况报告不仅涉及取或不取, 都还可以考虑取多少的问题报告 , 这些 情况报告叫做多重背包问题报告 (即每项物品有固定个数, 不可能 不止一另有一个, 不可能 每项物品完会 无限个, 则叫做完全背包问题报告 ). 这些 问题报告 一般用动态规划(Dynamic Programming, DP)的算法, 动态规划的话会涉及两方面, 都还可以满足这两方面, 都还可以使用动态规划(DP): 一是重叠子问题报告 , 二是最优子型态. 满足重叠子问题报告 , 我们才都还可以应用该算法除理重叠子问题报告 的重复计算, 这便是DP提高速率单位的关键所在, 否则也就没法应用的必要; 满足最优子型态, 我们才都还可以将原问题报告 分解为多个子问题报告 , 并在求取子问题报告 最优解的过程中计算原问题报告 的最优解. 二者缺一不可.

v[i][j]表示在前i件物品选取, 倒进容量为j的背包中, 最多都还可以放的物品价值, item[i]表示第i件物品的价值.

在具体到本题, 都还可以先排除物品总价值非偶数的情况报告, 接下来都还可以将总价值的一般视作背包的大小, 而每个物品的价值视作背包问题报告 中的体积, 本题并完会 求最优解, 只是判断最优解是是是否是是只是背包五种的大小, 很多很多 都还可以先求最优解, 再判断.

针对压缩前的每项物品取与不取共2^7=128种情况报告, 压缩后共2^3=8种情况报告, 压缩前各种情况报告不可能 取到的价值, 压缩后同样能取到, 如取1 ,3, 4, 5则价值为1+1+1+1=4, 则压缩后可用直接用取替代物品(压缩后)3来表示, 取1, 2 3, 4价值为1+1+1+1=4也都还可以用取替代物品3来表示, 再如取1, 2, 3, 4, 5, 6,7总价值为1+1+1+1+1+1+1=7, 都还可以表示为1+2+4=7, 即取替代物品1, 2, 3, 很多很多 对于每项压缩前情况报告, 压缩后均都还可以表示, 用替代物品的取与不取替代原来较多物品时取与不取的情况报告, 这便实现了压缩.

很多很多 , v[i-1][j]表示在前i-1件物品中找不大于j的最优解(即在前i件物品中不选取第i件再选取一点一点后的最优解), 而v[i-1][i-item[i]]表示在前i件物品中选取第i件再选取一点一点后的最优解.

以上是01背包问题报告 用动态规划算法求解时的分析, 而完全背包问题报告 我们都还可以转换为01背包问题报告 , 我们都还可以把同五种物品的每一另有一个视作不同种类, 原来原来第i中物品不可能 有k个, 现在都还可以理解为有k种不同的物品, 每项一另有一个, 原来每项物品的个数转换为一另有一个, 就变成了01背包问题报告 .

题目详见http://poj.org/problem?id=1014

具体代码如下(已Accepted): (参考了http://blog.csdn.net/zhu2mu/article/details/6649712)

压缩前                                          压缩后

还有一点只是这道题中限定总物品数最大为300000, 不可能 只用这些 思路不可能 会超时, 都还可以对算法加以优化, 减少需求解的情况报告, 这便用了网上所说的二进制压缩, 具体的证明应该在数论方面的书中, 是一另有一个定理, 大意是说, 任何一另有一个正整数, 均都还可以有一系列2的指数相加得到, 比如, 21 = 1 + 2 + 2 + 4 + 4 + 8 = 1 + 2*2 + 2*4 + 8 = 2^0 + 2*2^1 + 2*2^2 + 2^3. 依此定理, 每项物品的个数均都还可以没法表示, 但读者不可能 会问, 为这些 要原来表示? 是是因为是原来的, 首先我们用这些 定理的目的是压缩要求解的子问题报告 的个数, 这类于五种物品有2一另有一个, 不可能 单纯按多重背包转01背包的思路, 则新增了20中物品, 而利用二进制压缩, 我们都还可以将1件该种物品视为替代物品1, 将2件该种物品视为替代物品2, 将4件该种物品视为替代物品3, 依次类推, 原来转成的替代物品较少, 从而实现了压缩, 但一群人会担心, 按原来转化的方法, 每件物品取与不取的情况报告完会 考虑, 而二进制压缩完会 不必丢解呢, 这些 担心是多余的, 举例说明:

接下来说背包问题报告 的求解, 都还可以用下面的情况报告转移方程来表示问题报告 求解的思路:

给它们编号则为: (第一排为编号, 第二排为价值)

五种物品7个, 可用二进制压缩为 1 + 2 + 4,   即一另有一个物品变为替代物品1, 另有一个物品变为替代物品2, 另有一个物品变为替代物品3, 不可能 按原来不压缩的方法, 则变为 1 1 1 1 1 1 1共7个替代物品:

1   1   1   1   1   1   1                   1     2     4

1   2   3   4   5   6   7                   1     2     3

v[i][j] = max{v[]i-1[j], v[i-1][j-item[i]]+item[i]}