列表中其值总和最多为 K 的元素的最大数量，复杂度为 O(log n)

Question

我有这个练习要做：

设 M 为正整数，且 V = ⟨v1,... 。 。 , vn⟩ 有序向量 其中项 vi 的值为 5×i。

提出一个 O(log(n)) 算法，返回 V 中可以选择的最大项目数，前提是所选项目的总和小于或等于 M（不允许重复选择项目）。

首先我做了一个简单的解决方案：

• 我知道数组上的元素总和将始终小于数组上的 M/5 索引。于是 a 做了

  for i=0..i<=M/5

  并求出了总和。此外，这不是

  O(log(n))

  ，因为给定一个大 M，大于数组上所有元素的总和，它将是

  O(n).

因此我尝试了分而治之，我认为应该采用二分查找的方式。但实际上不是，因为如果我这样做，我将对可以选择到达 M 的最小元素求和，而不是最大值。我的代码如下

   def max_items_selected_recursive2(M, V, left, right, max):

    if len(V[left:right]) == 1:
      return max
    

    mid =  math.floor((left+right)/2)
    if  V[mid] >= M:
        return max_items_selected_recursive2(M - V[mid], V, mid + 1, right, max+1)
    else:
        if  M - V[mid] >= 0:
          return max_items_selected_recursive2(M - V[mid], V, left, mid - 1, max+1)
        else: 
          return max_items_selected_recursive2(M, V, left, mid - 1, max)
   

通话示例

M = 20
  V = [0, 5, 10, 15, 20]
  max_items_selected_recursive2(M, V, 0, len(V) - 1, 0) +1 # +1 since all have the O element

关于如何在 O(log n) 上执行此操作有什么想法吗？

Answer 1

总和 1 + 2 + ... + n = n * (n+1) / 2。

总和 5 + 10 + ... + 5n = 5 * (1 + 2 + ... + n) = 5 * n * (n+1) / 2。

因此，给定 M，我们想要求解 n，以便 5 * n * (n+1) / 2 <= M. Then, add 1 to this to account for zero.