POJ 1014 Dividing 解答

  • 时间:
  • 浏览:0

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

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

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

v[i][j]表示在前i件物品挑选 , 中放容量为j的背包中, 最多都只能放的物品价值, item[i]表示第i件物品的价值.

还有许多否则这道题中限定总物品数最大为40000, 意味 只用这种 思路意味 会超时, 只能对算法加以优化, 减少需求解的状况, 这便用了网上所说的二进制压缩, 具体的证明应该在数论方面的书中, 是一个多多多 多定理, 大意是说, 任何一个多多多 多正整数, 均都只能有一系列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个替代物品:

看了这道题第一反应便知道它是一道这种 背包现象的题,  解法我自然而然得从背包现象的解法入手,  网上查了查,  背包现象的基本题型是01背包, 即要素物品只能并都是, 好多好多 对于要素物品只能并都意味 , 取或不取, 而这道题不要再说符合01背包现象的条件, 题目中要素物品不止一个多多多 多, 好多好多 状况不仅涉及取或不取, 只能考虑取十哪几个 的现象, 这种 状况叫做多重背包现象(即要素物品有固定个数, 意味 不止一个多多多 多, 意味 要素物品都是无限个, 则叫做完全背包现象). 这种 现象一般用动态规划(Dynamic Programming, DP)的算法, 动态规划得话会涉及两方面, 只能满足这两方面, 能够使用动态规划(DP): 一是重叠子现象, 二是最优子形态学 . 满足重叠子现象, 让当我们 才都只能应用该算法防止重叠子现象的重复计算, 这便是DP提高时延的关键所在, 否则也就那么 应用的必要; 满足最优子形态学 , 让当我们 才都只能将原现象分解为多个子现象, 并在求取子现象最优解的过程中计算原现象的最优解. 二者缺一不可.

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

1   1   1   1   1   1   1                   1     2     4

压缩前                                          压缩后

在具体到本题, 都只能先排除物品总价值非偶数的状况, 接下来都只能将总价值的一般视作背包的大小, 而每个物品的价值视作背包现象中的体积, 本题并都是求最优解, 否则判断最优解是否否则背包并都是的大小, 好多好多 都只能先求最优解, 再判断.

以上是01背包现象用动态规划算法求解时的分析, 而完全背包现象让当我们 都只能转换为01背包现象, 让当我们 都只能把同并都是物品的每一个多多多 多视作不同种类, 原先原先第i中物品意味 有k个, 现在都只能理解为有k种不同的物品, 要素一个多多多 多, 原先要素物品的个数转换为一个多多多 多, 就变成了01背包现象.

针对压缩前的要素物品取与不取共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, 好多好多 对于要素压缩前状况, 压缩后均都只能表示, 用替代物品的取与不取替代原先较多物品时取与不取的状况, 这便实现了压缩.

1   2   3   4   5   6   7                   1     2     3

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