我什至不确定这是否可以在多项式时间内完成。
问题：
给定两个实数数组，
A = (a[1], a[2], ..., a[n]), B = (b[1], b[2], ..., b[n]), (b[j] > 0, j = 1, 2, ..., n)和一个数字
k，找到 的子集A'，A (A' = (a[i(1)], a[i(2)], ..., a[i(k)]))其中恰好包含k元素，使得(sum a[i(j)])/(sum b[i(j)])最大化，其中j = 1, 2, ..., k。
例如，如果k == 3,{a[1], a[5], a[7]}是结果，那么
(a[1] + a[5] + a[7])/(b[1] + b[5] + b[7])
应该大于任何其他组合。有什么线索吗？
假设 的条目B是肯定的（听起来这种特殊情况可能对您有用），有一个O(n^2 log n)算法。
让我们首先解决决定对于特定t的 是否存在这样的解决方案的问题
(sum a[i(j)])/(sum b[i(j)]) >= t.
清分母，这个条件等价于
sum (a[i(j)] - t*b[i(j)]) >= 0.
我们所要做的就是选择 的k最大值a[i(j)] - t*b[i(j)]。
现在，为了解决t未知时的问题，我们使用动力学算法。将t其视为时间变量；n我们对粒子具有初始位置A和速度的一维物理系统的演化感兴趣-B。每个粒子最多与其他粒子交叉一次，因此事件数为O(n^2)。在交叉点之间，最优值sum (a[i(j)] - t*b[i(j)])线性变化，因为相同的子集k是最优的。
如果 B 可以包含负数，那么这是 NP-Hard。
由于这个问题的 NP-Hardness：
给定 k 和数组 B，是否存在 B 的大小为 k 且总和为零的子集。
在这种情况下，A 变得无关紧要。
当然，从您的评论看来， B 必须包含正数。