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)上做到这一点有什么想法吗？

鉴于k，你能v1+v2+...+vk在头脑中快速计算吗？ — 
是的，但正如我之前所说，它是 O(n) 。我会喜欢 5+10+…直到 M，最坏情况下是 O(n)，当 M 大于或等于所有数组的总和时。这里的问题是在 log(n) 中查找，如问题中所解释的。抱歉，如果问题不清楚，我会尝试用粗体使其更明显 — 
“是的，但正如我之前所说，它的复杂度是 O(n)”。你的脑海中并没有很快想到这一点。在尝试编写一行代码之前，您需要能够在头脑中快速完成。 — 
所以你需要学习hopw才能做到这一点。这不是一个编程问题，这是一个数学问题。查找“算术级数之和” —

Accepted Answer

总和 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。然后，将其加 1 以将其归零。

您可以使用二次公式得到 O(1)（也是 O(log n)）解，或者对 n 进行二分搜索得到 O(log n) 解。

你好，谢谢你的回答！您能进一步开发二分搜索解决方案吗？ — 
@CatarinaNogueira 如果 M==0 则 n 为 0。否则，设置 n=1 并继续将 n 加倍，直到 5*n*(n+1)/2 > M。这需要 log 时间。现在您有了围绕您要查找的值的两个相邻的 2 的幂。正常的二分查找也在日志时间内进行。 — 
@CatarinaNogueira 也就是说，所有 O(1) 算法也是 O(n) 所以它更干净/更快/符合使用 O(1) 解决方案的要求。 —

Answer 2

使用Python的二分搜索的实现：

from bisect import bisect

M = 1_000_000
n = 10_000

print(bisect(
    range(n+1),
    False,
    key=lambda i: 5*i*(i+1)//2 > M
) - 1)

输出（）：

range 提供了可能的项目数量（0 到 n，包括），key 函数告诉给定的数字 i 是否太大。然后 bisect 找到太大的最小数，然后减去 1 以获得不太大的最大数。

你好！感谢分享。不幸的是，这对我没有帮助，因为我知道我应该进行二分搜索，但如果没有算术和，我无法创建算法。因此，使用算术和调用 python 函数与我之前所做的相同，但这里使用的是 python 函数。不管怎么说，还是要谢谢你：） — 
@CatarinaNogueira 有什么可以帮助你的？看起来你坚持做一些不可能的事情，而不是做练习希望你做的事情，而你为什么这样做仍然是个谜。 — 
我想解决不使用算术公式。如果不可能，好的，谢谢您的澄清。 — 
@CatarinaNogueira 你会得到这个练习的官方解决方案吗？我很好奇那是什么样子的。 —

Answer 3

根据 @dave 和 @nm 的建议，可以是使用算术和的 AI，我们下面的代码可以在 O(log n) 上使用算术和 + 二分搜索：

def max_items_selected_recursive2(M, V, left, right):
    if left == right:
      return left
    
    mid =  math.floor((left+right)/2) 

    arithmetic_med = 5* (mid*(mid+1)/2)

    arithmetic_med_plus_1 = 5* (mid+1*((mid+1)+1)/2)
    
    if arithmetic_med <= M and arithmetic_med_plus_1 >=M:
      return mid
    elif arithmetic_med <= M:
        return max_items_selected_recursive2(M, V, mid + 1, right)
    else:
        return max_items_selected_recursive2(M, V, left, mid - 1)

此外，我不想使用算术和，我只想使用纯二分搜索。这个我还是不知道该怎么办。

“我不想使用算术和” – 为什么？像这样的事情可能是预期的解决方案。 — 
因为我一开始并没有意识到这一点，所以我可以使用这个公式，我尝试不用这个公式，但我做不到。所以我真的很想知道该怎么做，这样我就能理解为什么我以前不能 — 
(1)(mid+1*((mid+1)+1)/2)我认为你不是这个意思。也许缺少一些括号？ (2) 我认为这并不完全正确，测试M=5,15,30,50,75,105。您需要获得连续的数字，但该程序输出 1,3,3,4,6,6。也许你想修改这个条件if arithmetic_med <= M and arithmetic_med_plus_1 >=M:。如果你得到了会发生什么arithmetic_med_plus_1 ==M？ — 
@nmcouldbeanAI 你说数组 5,15,30,50,75,105 不起作用？该算法返回 V 中可以选择的最大项目数，前提是所选项目的总和小于或等于 M 。 — 
另外，根据规范“其中项 vi 的值为 5×i”，所以你的数组实际上是无效的，它应该有 0、10 等 —

python – 列表中元素的最大数量，其值总和最多为 O(log n) 中的 K – VoidCC

3 个回答
3

3 个回答 3

3 个回答
3