如何在O(log n)时间内选取和不超过M的最多V向量元素？

设M为正整数，V = ⟨v₁, …, vₙ⟩是有序向量，其中元素vᵢ的值为5×i。请设计一个时间复杂度为O(log n)的算法，返回从V中可选取的最大元素个数，要求选取元素的总和小于等于M（元素不可重复选取）。

我的尝试 #

朴素解法 #

• 我知道数组元素的总和总是小于等于M/5对应的数组索引范围的和，因此通过for i=0..i<=M/5计算总和。但该解法时间复杂度不是O(log n)，当M远大于数组所有元素总和时，时间复杂度为O(n)。

分治尝试（未成功） #

我以为二分查找是可行方向，但实际走偏了——当前逻辑会优先选大元素，导致选到的元素个数不是最多的。我的代码如下：

import math

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 因为包含0元素

正确的O(log n)解法 #

要选最多元素，核心逻辑是优先选最小的元素——小元素的累加和增长更慢，能容纳更多个数。直接遍历小元素是O(n)，但我们可以通过数学推导+二分查找把复杂度降到O(log n)。

问题简化 #

每个元素vᵢ=5i，我们可以把总和限制M除以5，得到S = M // 5，问题等价于：从1到n（如果V包含0，有效元素是1到n-1）中选最多的数，它们的和≤S。0不影响总和，选了只会增加个数，最后结果加上1即可（如果V包含0）。

关键推导 #

前k个正整数的和公式是sum(k) = k*(k+1)/2。我们需要找到最大的k，满足sum(k) ≤ S：

1. 如果S大于等于所有有效元素的总和，那最大个数就是有效元素的总数（加0则再加1）。
2. 否则，用二分查找在[1, 有效元素总数]范围内找这个k。

实现代码 #

import math

def max_items(M, V):
    # 区分是否包含0元素，确定有效元素的数量
    has_zero = V[0] == 0 if len(V) > 0 else False
    actual_n = len(V) - 1 if has_zero else len(V)
    S = M // 5

    # 处理无法选任何非0元素的情况
    if S < 1:
        return 1 if has_zero else 0

    # 计算所有有效元素的总和
    total_sum = actual_n * (actual_n + 1) // 2
    if S >= total_sum:
        return actual_n + (1 if has_zero else 0)

    # 二分查找最大的k
    left, right = 1, actual_n
    best_k = 0
    while left <= right:
        mid = (left + right) // 2
        current_sum = mid * (mid + 1) // 2
        if current_sum <= S:
            best_k = mid
            left = mid + 1  # 尝试更大的k
        else:
            right = mid - 1  # 太大了，缩小右边界

    return best_k + (1 if has_zero else 0)

测试验证 #

• 输入M=20, V=[0,5,10,15,20]：S=4，最大k=2（sum(2)=3≤4），加上0总个数3，符合预期（比如选0+5+10=15≤20）。
• 输入M=30, V=[5,10,15,20]：S=6，sum(3)=6≤6，总个数3，总和5+10+15=30，正确。
• 输入M=100, V=[5,10,15,20,25]：sum(5)=15≤20（S=20），总个数5，总和75≤100，正确。

内容的提问来源于stack exchange，提问作者Catarina Nogueira