作者fatcat8127 (胖胖猫)
看板Prob_Solve
标题[问题] 请教zerojudge c824 / c835 的背包问题
时间Wed Feb 27 00:35:38 2019
如题，这两题的题目叙述和要求都是相同的，但特别之处在於物品的重量和背包负重都是2
的次方项，要求和01背包问题一样问价值总和最大化。
想问一下解题方向或是想法，自己google了一下没看到有题解也不知道怎麽下关键字和01背
包做区隔，先谢谢各位大大的回覆。
因为输入的物品数量高达1e6个，而且重量和2的次方项有关，就异想天开想说会不会和
Huffman-Code 的编码方式有关，所以写了一个初版本，通过51%测资而已。
以下是我的程式码：
https://www.codepile.net/pile/A71bYyDz
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.113.208.164
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1551198940.A.FA1.html
※ 编辑: fatcat8127 (36.226.99.91), 02/27/2019 04:20:18
※ fatcat8127:转录至看板 C_and_CPP 02/27 05:14
1F：推 oToToT: 对於重量2^k时，我们把价值最大的两个合在一起凑出重量2^{ 02/27 19:52
2F：→ oToToT: k+1}的物品，一直做到重量2^k的剩下一个或零个。如果剩一 02/27 19:52
3F：→ oToToT: 个我们再考虑加入一个重量2^k价值为0的物品，让剩的那个也 02/27 19:52
4F：→ oToToT: 可以合上去，这样直接看重量2^M中，价值最大的那个物品就 02/27 19:52
5F：→ oToToT: 好。因为可以证明在每个重量最多加入一个价值为0的东西时 02/27 19:52
6F：→ oToToT: ，用最优解选完选到一些价值为0的东西并不会影响答案 02/27 19:52
8F：→ fatcat8127: 感谢大大的说明和程式码 02/28 01:52
9F：→ fatcat8127: 根据我自己的理解和今天讨论区的回覆，解法就是建立B 02/28 03:57
10F：→ fatcat8127: inominal Heap的过程吗 02/28 03:57