关于背包问题的一个思考

我在看背包问题9讲（很推荐没看过的同学去搜一下读读）其中讲到把完全背包问题转化为01背包问题可以通过把第i 种物品拆成费用为Ci * 2^k、价值为Wi * 2^k 的若干件物品，其中k 取遍满足Ci * 2^k <= V 的非负整数。Ci是第i个物品的cost，Wi是weight，V是最大允许的所有物品的Cost的总和。

文章说道：这是二进制的思想。因为，不管最优策略选几件第i 种物品，其件数写成二进制后，总可以表示成若干个2k件物品的和。我一开始不太理解这一块，后来举了个例子后有点开窍，把思考过程发到这里请大家指正。

假设我有一个物品i，它的Cost是3,Weight是2。V是24。那么我可以把这个物品拆成如下的若干个物品，并分别命名：

k=0: Ci= 3*2^0 = 3, Wi= 2*2^0 =2 取名i
k=1: Ci= 3*2^1 = 6, Wi= 2*2^1 =4 取名i'1
k=2: Ci= 3*2^2 = 12, Wi= 2*2^2 =8 取名i'2

这样的话，我可以取一个i，它的cost是3，这是最基本的case。或者我可以取2个i（物品i'1），Cost是6。或者我可以取4个i（物品i'2），cost是12。到这个时候，我并没有哪个物品可以代表3个i的状态，这就是这种拆分方法的精妙之处：3个i的状态可以由 i + i'1获得。我们继续计算k：

k=3: Ci= 3*2^3 = 24 (与V相等，这时终止计算更多的k), Wi= 2*2^3 =16 取名i'3

i'2和i'3是从k=2到k=3，它们的cost直接从12跳到了24，这中间的空当可以由之前的i,i'1,i'2相加来填充。比如，当你想要cost是21时，你可以用一个i'2(Cost是12)加上一个i'1(cost是6)加上一个i(cost是3)来组合。

其实任意一个正整数都可以表示为不同的多个2的n次方数的和。例如7 = 1 + 2 + 4.

原因可以联想一下二进制的表达方式。在你把十进制数转化为二进制数的时候，例如7 = 1 * 2^2 + 1 * 2^1 + 1 * 2^0 = 111 (2)，对于2^i (i = 0, 1, 2, 3, ...)，前面的因数只有0或1两种，毕竟二进制下超过1的数字都要进位。所以当把任意自然数转化为二进制的时候，只可能表示为多个不同的2的幂次的和。

lalxyy 发表于 2020-4-12 09:36
其实任意一个正整数都可以表示为不同的多个2的n次方数的和。例如7 = 1 + 2 + 4.

原因可以联想一下二进 ...

嗯嗯，谢谢补充