为什么任意整数都能表达成2^k的形式?

回复帖子

@AMIRIOX無暝 2020-11-21 23:01 回复

看完全背包, 看到一个

更高效的转化方法是:把第i 种物品拆成费用Ci 2^k、价值为Wi 2^k 的若干件物品,其中k 取遍满足Ci*2^k ≤ V 的非负整数。这是二进制的思想。因为,不管最优策略选几件第i 种物品,其件数写成二进制后,总可以表示成若干个2^k 件物品的和。

这个好像是快速幂里面的内容, 但当时学非递归快速幂的时候我就没学太明白, 求问为什么"不管最优策略选几件第i 种物品,其件数写成二进制后,总可以表示成若干个2^k 件物品的和。"啊

@小粉兔  管理员 2020-11-21 23:04 回复 举报

最优策略选的物品 $i$ 的数量 $x$ 满足 $0 \le x \le V / C_i$

然后 $k$ 的最大值是 $\log_2 V / C_i$。

然后你把 $x$ 二进制拆分就能发现了

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。