对背包问题的一些研究.doc

对背包问题的一些研究
江苏靖江高级中学 李哲
我们对背包问题都很熟悉，这次我们要讨论的是背包问题中的01背包，即在一个容量为c的背包中，放入n个物体，这n个物体重量为w[1..n]，价值为v[1..n]，要求在不超过容量限制的情况下最大的价值是多少。
对于重量为整数的背包问题我们可以很快写出动态规划方程：
f[i,j]=max{f[i-1,j],f[i-1,j-w[i]]+v[i]}
其中f[i,j]表示前i个物体用j个空间时能获得的最大价值。但是这有一个很大的缺点，就是对于容量很大的数据就会花费太多的时间，而且如果重量是实数而不是整数就根本无法进行。
对于这个问题，我曾看到一本书上提供了用函数间断点的方法来解决。基本思路是对于当前的情况，用一系列二元组来描述。二元组是（w,v）的形式，表示重量为w时最大价值为v。每加入一个新的物体时，对当前的所有二元组进行拓展，并和原来的合并得到新的二元组集。
如：
容量为10，有5个物体，重量为3 5 1 9 7，价值为11 28 6 49 35。则二元组集p的变化为
0个物体时
p={(0,0)}
加入第1个物体时
q={(3,11)}
p={(0,0),(3,11)}
加入第2个物体时
q={(5,28),(8,39)}
p={(0,0),(3,11),(5,28),(8,39)}
加入第3个物体时
q={(1,6),(4,17),(6,34),(9,45)}
p={(0,0),(1,6),(4,17),(5,28),(6,34),(8,39),(9,45)}
加入第4个物体时
q={(9,49),(10,55)}
p={(0,0), (1,6),(4,17),(5,28),(6,34),(8,39),(9,49),(10,55)}
加入第5个物体时
q={(7,35),(8,43)}
p={(0,0), (1,6),(4,17),(5,28),(6,34), (7,35) ,(8,39), (9,49),(10,55)}
所以最大价值为55，这与我们用动态规划的出的结论是一样的。动态规划表格如下：
0
0
11
11
11
11
11
11
11
11
0
0
11
11
28
28
28
39
39
39
6
6
6
17
28
34
34
39
45
45
6
6
6
17
28
34
34
39
49
55
6
6
6
17
28
34
35
39
49
55
而我们得到二元组集正是这个函数的间断点分布。
当时看这个算法时，书上介绍其时间复杂度为O(2n)。因为每次加入一个物体会使当前的二元集扩大到2倍左右。但是事实上没有那么恐怖，因为有以下两个限制条件帮我们大量剪枝：
1． 当重量超过限制时去掉
2． 当出现(ai,bi)和(aj,bj)，并有ai<aj且bi>bj时去掉后者
由此可见，要想提高算法的效率，主要要利用这两个限制条件，因此我们可以在计算前先排一个序。那么根据什么作为排序的key呢？首先要明确的是，我们要尽量在靠近树根的地方把枝剪掉，这样才能剪去一片“茂密”的树叶。从第一个限制条件看，要尽量把重的物体放在前面，才能有效地利用这一条件。从第二个限制条件看，我们要尽量把单价高地放在前面，才可能出现尽可能多得逆序对。所以我们的key应该有两部分构成，w和v/w，可以写成key=a*w+b*v/w。在重量相对于背包较大时，可以使a的值高一些，而在单价变化相对明显的情况下则可以提高b的值。当然如果不想写这样的判定，我们可以用随机算法，效果也不错。
经过我自己多次试验后，发现这个算法的复杂度大约在n2.4左右，在处理实数重量和大重量的背包问题时还是很方便的。