Untitled

mail@pastecode.io avatar
unknown
python
6 months ago
1.4 kB
3
Indexable
Never
def max_requests_dp(total_bandwidth, bandwidth, request):
    dp = {}
    def dfs(i, remaining_bandwidth):
        if i == len(bandwidth):
            return 0
        if i in dp:
            return dp[(i, remaining_bandwidth)]
        if bandwidth[i] > remaining_bandwidth:
            dp[(i, remaining_bandwidth)] = dfs(i+1, remaining_bandwidth)
            return dp[(i, remaining_bandwidth)]
        else:
            dp[(i, remaining_bandwidth)] =  max(dfs(i +1 , remaining_bandwidth), dfs(i +1 , remaining_bandwidth-bandwidth[i])+request[i]) 
            return dp[(i, remaining_bandwidth)]
            
    return dfs(0, total_bandwidth)

def max_requests_optimal(total_bandwidth, bandwidth, request):
    n = len(bandwidth)

    # Create a list of tuples (endpoint, bandwidth, request, ratio)
    # endpoints = [(i, bandwidth[i], request[i], request[i]) for i in range(n)]
    endpoints = zip(bandwidth, request)

    # Sort endpoints by the ratio in descending order
    sorted_endpoints = sorted(endpoints, key=lambda x: x[1], reverse=True)

    max_requests_served = 0

    for i in range(n):
        bw, req = sorted_endpoints[i]

        bandwidth_allocated = min(bw, total_bandwidth)
        if bw <= total_bandwidth:
            requests_served = req
            max_requests_served += requests_served
            total_bandwidth -= bandwidth_allocated

    return max_requests_served