I have this exercise to do:

Let M be a positive integer, and V = ⟨v1, . . . , vn⟩ an ordered vector where the value of item vi is 5×i.

Present an O(log(n)) algorithm that returns the maximum number of items from V that can be selected given that the sum of the selected items is less than or equal to M (repeated selection of items is not allowed).

First I did a naive solution where:

• I know the sum of elements on the array will be always less than the M/5 index on the array. So a did for i=0..i<=M/5 and found the sum. Moreover this is not O(log(n)) because given a big M, bigger than the sum of all elements on the array, it will be O(n).

Therefore I tried divide and conquer, I thought a binary search should be the way. But actually no because if I do that I will sum the minimum elements that can be chosen to arrive in M, not the maximum. My code is below

   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)
   

example of call

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

Any ideas?