POJ1014: 多重背包 + 二进制优化 + 取模优化

ゝ一世哀愁。 2021-10-25 14:24 254阅读 0赞

######  ######

###### **问题描述：** ######

有若干价值为分别为1，2 ，3，4，5，6的大理石，求总价值的均分策略。设价值为V的石头重量为V,这批石头的总价值为SUM,则问题转化为选取若干大理石将容量为SUM/2的背包装满。

###### **背包问题（参考“背包问题9讲”）** ######

有N件物品和一个容量为V的背包，第i件物品的费用是c\[i\]，价值是w\[i\]。 f\[i\]\[v\]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值,则有：

**0-1背包**

<table> 
 <tbody> 
  <tr> 
   <td align="center">状态转移方程 </td> 
   <td>f[i][v] = max{f[i-1][v], f[i-1][v-c[i]]+w[i]}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </td> 
  </tr> 
  <tr> 
   <td align="center">解法 O(VN)</td> 
   <td>for i = 1…N <br>&nbsp;&nbsp;&nbsp; for v = V…c[i] <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; f[v] = max{f[v], f[v-c[i]]+w[i]};</td> 
  </tr> 
  <tr> 
   <td align="center">子过程</td> 
   <td>procedure ZeroOnePack(cost, weight) <br>&nbsp;&nbsp; for v = V…cost <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; f[v] = max{f[v], f[v-cost]+weight}</td> 
  </tr> 
  <tr> 
   <td align="center">初始化</td> 
   <td>要求恰好装满背包： f[0] = 0, f[1…V] = –1 <br>只要求价值最大:&nbsp;&nbsp; f[0…V] = 0&nbsp; </td> 
  </tr> 
 </tbody> 
</table>

**完全背包**

<table> 
 <tbody> 
  <tr> 
   <td align="center">状态转移方程&nbsp; O(V*Σ(V/c[i]))</td> 
   <td>f[i][v] = max{f[i-1][v-k*c[i]]+k*w[i]|0&lt;=k*c[i]&lt;=v} </td> 
  </tr> 
  <tr> 
   <td align="center">转化为0-1背包问题 O(VN)</td> 
   <td>for i = 1…N <br>&nbsp;&nbsp;&nbsp; for v = cost…V <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; f[v] = max{f[v], f[v-cost]+weight}</td> 
  </tr> 
  <tr> 
   <td align="center">子过程</td> 
   <td>procedure CompletePack(cost, weight) <br>&nbsp;&nbsp;&nbsp;&nbsp; for v = cost…V <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; f[v] = max{f[v], f[v-cost]+weight}</td> 
  </tr> 
 </tbody> 
</table>

**多重背包 (指定每件物品的个数n\[i\])**

<table> 
 <tbody> 
  <tr> 
   <td align="center">状态转移方程 O(V*Σn[i])</td> 
   <td>f[i][v] = max{f[i-1][v-k*c[i]]+k*w[i]|0&lt;=k&lt;=n[i]}</td> 
  </tr> 
  <tr> 
   <td align="center">二进制优化 O(V*Σlog(n[i]))</td> 
   <td>将第i种物品以2的指数分堆：1，2，4，…，2^(k-1)，n[i]-2^k+1,且 <br>k是满足n[i]-2^k+1&gt;0的最大整数。每次处理一堆而不是一个物品。</td> 
  </tr> 
  <tr> 
   <td align="center">伪代码</td> 
   <td>procedure MultiplePack(cost, weight, amount) <br>&nbsp;&nbsp;&nbsp; if cost*amount&gt;=V <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; CompletePack(cost, weight) <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return <br>&nbsp;&nbsp;&nbsp; integer k=1 <br>&nbsp;&nbsp;&nbsp; while k&lt;amount <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ZeroOnePack(k*cost, k*weight) <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; amount = amount – k <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; k = k * 2 <br>&nbsp;&nbsp;&nbsp; ZeroOnePack(amount*cost, amount*weight)</td> 
  </tr> 
 </tbody> 
</table>

######  ######

###### **取模优化** ######

当输入样本特别大时，比如给出上百万件物品，这时候仅靠优化算法仍然不能使运行时间降到满意的范围。可考虑如何减少输入样本。poj1014的discussion上有一个非常巧妙的“取模优化”法。

设价值为v(1<=v<=6)的物品共有n件，我们希望找到一个比较小的数s(s<n), 且将n件物品v减少到s或s-1件，问题的可分性不变。考虑不可分和可分两种情况：

1.  如果该问题不可分，那么n-2件v仍然不可分，依次类推，用s或 s-1替换n仍然不可分
2.  如果该问题可分，即可分成价值相等的两堆。分两种情况考虑：

*  如果两堆里都有v。 两堆各减一个v，即n改为n-2,仍然可分，可以反复减2直至只有一堆有v。
 *  如果仅有一堆有v。 如果将n改为n-2仍可分，则必须满足两个条件： I.没有v的那一堆中，至少有一种其它物品可替换v。II.替换后两堆都至少有一个v。如果n>s时始终满足这两个条件，我们就可以用s或s-1替换n.

下面依次考虑v=1,2,3,4,5,6时如何根据“抽屉原理”得到满足条件I和II的s。

**v=1时，s=6   替换法： if(n>6) n=6-n%2**

1总能被其它价值替换，所以满足条件I不是问题，为满足条件2，s必须大于6。 因为6是其它价值物品中一次可替换最多1的物品。

**v=2时，s=5   替换法： if(n>5) n=4+n%2**

由1\*(2-1)+3\*(2-1)+4\*(1-1)+5\*(2-1)+6\*(1-1) = 9 < 2\*5知，s=4时满足条件I。但这里要注意，如果另一堆可替换2的是两个5，那么一次就可替换5个2。为满足条件 II,s不能小于5。所以这里s是5而不是4。

**v=3时，s=8    替换法： if(n>8) n=8-n%2**

由1\*(3-1)+2\*(3-1)+4\*(3-1)+5\*(3-1)+6\*(1-1) = 24 < 3\*9知，s=8时满足条件I，且最多可替换5个3，所以s=8>5也满足条件II。

**v=4时，s=8    替换法： if(n>8) n=8-n%2**

由1\*(4-1)+2\*(2-1)+3\*(4-1)+5\*(4-1)+6\*(2-1) = 35 < 4\*9知， s=8时满足条件I，且最多可替换5个4，所以s=8>5也满足条件II。

**v=5时，s=12   替换法： if(n>12) n=12-n%2**

由1\*(5-1)+2\*(5-1)+3\*(5-1)+4\*(5-1)+6\*(5-1) = 64 < 5\*13知，s=12满足条件I，且最多可替换6个5，所以s=12>6也满足条件II。

**v=6时，s=7   替换法：if(n>7) n=6+n%2**