Maximum items with given k tokens

user_3181365 0
Viewed 2798

I have N elements in array. I can select the first item max of N times, the second item max of N-1 times and so on.

I have K tokens to use and need to use them so I can have the maximum number of items.

arr = [3, 4, 8] where array elements indicates tokens required for i'th item

    n = 10 , represents number of tokens I have

Output:

    3

Explanation:

We have 2 options here:

1. option 1: 1st item 2 times for 6 tokens (3*2) and second item once for 4 tokens (4*1)

2. option 2: 1st item 3 times for 9 tokens (3*3)

so maximum we can have 3 items

Code:

def process(arr,n):
    count = 0
    sum = 0
    
    size = len(arr)+1
    for i in range(0, len(arr), 1):
        size1 = size-1
        size -= 1
        while((sum+arr[i] <= n) and (size1 > 0)):
            size1 = size1 -1
            sum = sum + arr[i]
            count += 1

    return count;

But it worked for only few test cases, it failed for some hidden test cases. I am not sure where I made a mistake. Can anybody help me?

algorithm python
4 Answers

Your greedy approach will fail for the test cases like this:

[8,2,1,1] 10

Your code will return 2 but the maximum will be 6.

I will use a heap of a tuple i.e. heap[(cost_of_ride,max_no_rides)] .

See the code below:

from heapq import *

def process(arr,n):
    count = 0
    
    heap = []
    
    for i in range(len(arr)):
        heappush(heap,(arr[i],-(len(arr)-i))) # Constructing min-heap with second index as negative of maximum number of rides 
    
    while(n>0 and heap):
        cost,no_of_rides = heappop(heap)
        no_of_rides = -1 * no_of_rides # Changing maximum no_of_rides from negative to positive
        
        div = n//cost

        # If the amount of money is not sufficient to calculate the last number of rides user could take
        if(div<no_of_rides):
            count += div
            break

        # Else decrement the number of tokens by minimum cost * maximum no_of_rides
        else:
            count += no_of_rides
            n -= no_of_rides*cost
    

    return count;

Time Complexity for the solution is: O(len(arr)*lg(len(arr))) or O(N*lg(N)).

user_136519780

Try:

def process(arr, n, res=[]):
    l=len(arr)
    for j in range(len(arr)+1):
        r=[arr[0]]*j
        if(sum(r)==n) or (sum(r)<n) and (l==1):
            yield len(res+r)
        elif(sum(r)<n):
            yield from process(arr[1:], n-sum(r), res+r)
        else:
            break

The idea is to iterate over all possible combinations of resulting tokens, more precisely - all options for individual token are just this token taken between 0 and N times, where N refers to tokens position, per your logic. Discarding on the way combinations, which exceed n, ultimately returning generator, which produces lengths of produced vector of all tokens taken in all possible quantities (so in order to address your question - you need to take max(...) from it).

Outputs:

>>> print(max(process([3,4,8],10)))

3

>>> print(max(process([8,2,1,1],10)))       

6

>>> print(max(process([10, 8, 6, 4, 2], 30)))

6
user_116101860

@learner your logic doesn't seem to be working properly.
Please try these inputs: arr = [10, 8, 6, 4, 2], n = 30.
As per your description answer should be 6 rides but your code would produce 3

user_138894130

Use a modified form a quickselect, where you select the next pivot based on the sum of the products of cost * max_times, but still sort based on just cost. This is worst-case O(n^2), but expected O(n).

user_20410770
Related