我有这个练习要做:
设M为正整数，V = v1，.. .，vn假设有序载体where the value of item vi is 5×i.
提出一个O(log(n))算法，该算法返回V中可以 Select 的最大项目数，前提是所选项目的总和小于或等于M(不允许重复 Select 项目).
首先我做了一个天真的解决方案:
- 我知道数组上的元素之和将始终小于数组上的M/5索引.所以a做了
for i=0..i<=M/5并找到了总和.此外，这不是O(log(n))，因为给定一个大M，大于数组上所有元素的总和，它将是O(n).
因此我try 了分而治之，我认为二分法应该是办法.但实际上不是，因为如果我这样做，我将对可以 Select 以得到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)上做到这一点有什么 idea 吗？