Written with StackEdit.
Reference:https://leomalik.github.io/01%E8%83%8C%E5%8C%85%E3%80%81%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E3%80%81%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85.html See Also: https://www.kancloud.cn/kancloud/pack/70128 之前提到了DP背包问题,很多文章都提到了可以转化为最简单的0/1背包求解.翻找了很多文章都不理想,找到了这一篇文章讲解的比较透彻,在这里写一些体会.
每件物品转换为 [ W / w [ i ] ] [W/w[i]] [W/w[i]]件相同物体,其中W固定为输入的最大重量(考虑到最优解可能是只挑一种) 但这种算法并未优化时间复杂度.
把第i种物品拆成费用为 c [ i ] ∗ 2 k c[i]*2^k c[i]∗2k、价值为 w [ i ] ∗ 2 k w[i]*2^k w[i]∗2k的若干件物品，其中k满足c[i]*2^k<=V. 这里是二进制的思想. O c t = ∑ ( 0 / 1 ) × w e i g h t Oct=\sum (0/1)\times weight Oct=∑(0/1)×weight(这里Oct是最后选择的 总量 示例: Weight=16,Value=12,Maxweight=100 分解为如下: (16,12) (32,24) (64,48)
基准方式: 每个物品有k个,则分解为k个单独物品(并没什么用)
改进方式:依然使用二进制. 拆分为 w e i g h t = w [ i ] ∗ 2 k , v a l u e = v [ i ] ∗ 2 k weight=w[i]*2^k,value=v[i]*2^k weight=w[i]∗2k,value=v[i]∗2k的物品,要求 w e i g h t ≤ m a x w e i g h t weight\leq maxweight weight≤maxweight且 2 k + 1 − 1 ≤ m a x q u a n t i t y 2^{k+1}-1\leq maxquantity 2k+1−1≤maxquantity(为了保证全选依然可行).
