Algorithmic Toolbox | Week 3

Course Name: Algorithmic Toolbox

These are Algorithmic Toolbox Week 3 Programming Assignment Coursera Answers

Programming Assignment 3: Greedy Algorithms

3-1: Money Change

def get_min_coins(money):
    # Define the denominations
    denominations = [10, 5, 1]
    num_coins = 0
    
    # Iterate over each denomination
    for coin in denominations:
        if money == 0:
            break
        num_coins += money // coin
        money %= coin
    
    return num_coins

if __name__ == '__main__':
    money = int(input().strip())
    print(get_min_coins(money))

These are Algorithmic Toolbox Week 3 Programming Assignment Coursera Answers

3-2: Maximum Value of the Loot (Fractional Knapsack)

def get_max_value(capacity, weights, values):
    # Calculate value to weight ratio
    items = []
    for i in range(len(weights)):
        if weights[i] != 0:
            items.append((values[i] / weights[i], weights[i], values[i]))

    # Sort items by value to weight ratio in descending order
    items.sort(reverse=True, key=lambda x: x[0])
    
    total_value = 0.0
    for value_per_weight, weight, value in items:
        if capacity == 0:
            break
        amount = min(weight, capacity)
        total_value += amount * value_per_weight
        capacity -= amount
    
    return total_value

if __name__ == '__main__':
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    capacity = int(data[1])
    
    weights = []
    values = []
    for i in range(n):
        values.append(int(data[2 + 2*i]))
        weights.append(int(data[2 + 2*i + 1]))
    
    max_value = get_max_value(capacity, weights, values)
    print(f"{max_value:.4f}")

These are Algorithmic Toolbox Week 3 Programming Assignment Coursera Answers

3-3: Car Fueling

def min_refills(distance, tank, stops):
    # Add start (0) and end (distance) to the list of stops
    stops = [0] + stops + [distance]
    
    num_refills = 0
    current_position = 0
    
    while current_position < len(stops) - 1:
        last_refill_position = current_position
        
        # Move to the furthest reachable stop
        while (current_position < len(stops) - 1 and
               stops[current_position + 1] - stops[last_refill_position] <= tank):
            current_position += 1
        
        # If no progress is made, it means the next stop is unreachable
        if current_position == last_refill_position:
            return -1
        
        # If we haven't reached the last stop, we need a refill
        if current_position < len(stops) - 1:
            num_refills += 1
    
    return num_refills

if __name__ == '__main__':
    import sys
    input = sys.stdin.read
    data = input().split()
    
    d = int(data[0])
    m = int(data[1])
    n = int(data[2])
    stops = list(map(int, data[3:3 + n]))
    
    result = min_refills(d, m, stops)
    print(result)

These are Algorithmic Toolbox Week 3 Programming Assignment Coursera Answers

See also Algorithmic Toolbox | Week 6

3-4: Maximum Advertisement Revenue (Maximum Dot Product)

def max_dot_product(prices, clicks):
    # Sort both sequences
    prices.sort()
    clicks.sort()
    
    # Calculate the dot product
    max_product = sum(p * c for p, c in zip(prices, clicks))
    
    return max_product

if __name__ == '__main__':
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    prices = list(map(int, data[1:n+1]))
    clicks = list(map(int, data[n+1:2*n+1]))
    
    result = max_dot_product(prices, clicks)
    print(result)

These are Algorithmic Toolbox Week 3 Programming Assignment Coursera Answers

3-5: Collecting Signatures (Covering Segments by Points)

def cover_segments(segments):
    # Sort segments by their right endpoint
    segments.sort(key=lambda x: x[1])
    
    points = []
    current_point = None
    
    for segment in segments:
        if current_point is None or segment[0] > current_point:
            current_point = segment[1]
            points.append(current_point)
    
    return points

if __name__ == '__main__':
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    segments = []
    index = 1
    for i in range(n):
        l = int(data[index])
        r = int(data[index + 1])
        segments.append((l, r))
        index += 2
    
    points = cover_segments(segments)
    print(len(points))
    print(' '.join(map(str, points)))

These are Algorithmic Toolbox Week 3 Programming Assignment Coursera Answers

3-6: Maximum Number of Prizes (Different Summands)

def find_maximum_k(n):
    summands = []
    current_sum = 0
    current_number = 1
    
    while current_sum + current_number <= n:
        summands.append(current_number)
        current_sum += current_number
        current_number += 1
    
    # Adjust the last number if the sum is not exactly n
    if current_sum < n:
        summands[-1] += (n - current_sum)
    
    return summands

if __name__ == '__main__':
    n = int(input())
    result = find_maximum_k(n)
    print(len(result))
    print(' '.join(map(str, result)))

These are Algorithmic Toolbox Week 3 Programming Assignment Coursera Answers

3-7: Maximum Salary (Largest Number)

from functools import cmp_to_key

def largest_number(numbers):
    # Custom comparison function
    def compare(a, b):
        if a + b > b + a:
            return -1
        elif a + b < b + a:
            return 1
        else:
            return 0
    
    # Convert numbers to strings for concatenation
    numbers = list(map(str, numbers))
    
    # Sort numbers using the custom comparison function
    numbers.sort(key=cmp_to_key(compare))
    
    # Concatenate the sorted numbers
    largest_num = ''.join(numbers)
    
    # To handle the case where there are leading zeros (e.g., [0, 0])
    return '0' if largest_num[0] == '0' else largest_num

if __name__ == '__main__':
    n = int(input())
    numbers = list(map(int, input().split()))
    print(largest_number(numbers))

These are Algorithmic Toolbox Week 3 Programming Assignment Coursera Answers

These are Algorithmic Toolbox Week 3 Programming Assignment Coursera Answers

Programming Assignment 3: Greedy Algorithms

Similar: