0-1线性分式规划问题(0-1 ILFP)问题有保证性能的近似算法吗

2020-08-03

如果所有w都是正整数的话，用整数背包的伪多项式算法的思路容易能想到一个动态规划的O（nW）的伪多项式算法，抛砖引玉吧。不妨设w\u0026#39;=max wi。则首先我们能知道，最优解的重量是不能超过W+w\u0026#39;的，因为如果超过的话，我们总能从里面删除vi/wi最小的一个，使得重量仍然超过w，而平均价值上升。令V〔k〕〔w〕为前k个货物中，重量和为w的子集的最大价值。则我们只需要求出V〔n〕〔W〕，V〔n〕〔W+1〕...V〔n〕〔W+w\u0026#39;〕，然后分别计算平均价值，求出最大的一个即可。而计算V〔i〕〔w〕可以用动态规划。首先V〔1〕〔w〕=v1，如果w=w1；=0如果w=0；等于负无穷，其他情况。然后V〔i〕〔w〕=max（V〔i-1〕〔w-wi〕+vi，V〔i-1〕〔w〕）。然后动态规划一层层算上去就是。需要O（n（W+w\u0026#39;））的时间。如果w\u0026#39;\u0026lt;W，则需要O（nW）的时间即可。若不然，则最优解中最多含有一个超过W的元素。把重量超过W的元素单独取出来，剩下的按照原方法做，再加上简单的讨论也能把时间控制在O（nW）。

推荐阅读

上一篇：豆瓣电台/虾米电台等怎样评估个性化电台的效果?

下一篇：有人给我冲了一块钱话费是咋回事