多重背包的取模优化

桃扇骨 2022-08-03 05:18 145阅读 0赞

取模优化

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

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

*  如果该问题不可分，那么n-2件v仍然不可分，依次类推，用s或 s-1替换n仍然不可分

*  如果该问题可分，即可分成价值相等的两堆。分两种情况考虑：

*  如果两堆里都有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

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

可以看出，“模优化”将无论多么大的输入样本减少到50个以内，极大地减少了计算量，从而显著提高运行效率。而“模优化”的关键就是“抽屉原理”。

发表评论取消回复

表情：

评论列表（有 0 条评论，145人围观）

还没有评论，来说两句吧...

相关阅读

相关多重背包问题

多重背包问题 1、参考资料 https://blog.csdn.net/qq\_38984851/article/details/81133840 https:/

╰半夏微凉°/ 2022年11月27日 07:24/ 0 赞/ 209 阅读

相关 01背包完全背包多重背包的概念

01背包（ZeroOnePack）: 有N件物品和一个容量为V的背包，每种物品均只有一件。第i件物品的费用是c\[i\]，价值是w\

港控/mmm°/ 2022年08月07日 11:46/ 0 赞/ 227 阅读

相关 Coins（多重背包+二进制优化）

Coins Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Oth

客官°小女子只卖身不卖艺/ 2022年08月03日 05:24/ 0 赞/ 167 阅读

相关 Dividing(多重背包+二进制优化)

Dividing <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td

小咪咪/ 2022年08月03日 05:22/ 0 赞/ 141 阅读

相关多重背包的取模优化

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

桃扇骨/ 2022年08月03日 05:18/ 0 赞/ 146 阅读

相关多重背包

问题：一个容量为c的背包，还有一些物品（每个物品有具体的数量num），这些物品的体积w和价值v各不相同。求出能在不超过c的情况下尽可能的使价值最大。对于多重背包问题，可

妖狐艹你老母/ 2022年05月31日 01:19/ 0 赞/ 208 阅读

相关多重背包

n个物品，每个可以取k次，容量为w，价值为v。一般做法：二进制拆分：将每个物品拆成O(log k)个01背包的物品，时间复杂度为(nmlogk) 例如：K=10 可以拆分

矫情吗；*/ 2021年12月23日 11:05/ 0 赞/ 329 阅读

相关多重背包问题

转自：[http://www.cnitblog.com/luckydmz/archive/2008/08/06/47719.aspx][http_www.cnitblog.co

青旅半醒/ 2021年12月16日 12:39/ 0 赞/ 295 阅读

相关多重背包二进制优化

多重背包二进制优化将\\(num\\)件，价值\\(v\\)，花费\\(cost\\)的物品\\((v,w)\\)拆分为\\((v,w),(v\\times 2^1,w

迈不过友情╰/ 2021年12月03日 18:39/ 0 赞/ 236 阅读

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

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

ゝ一世哀愁。/ 2021年10月25日 14:24/ 0 赞/ 285 阅读