Algorithmic Toolbox | Week 6

2 years ago

user

3 minutes

Course Name: Algorithmic Toolbox

Course Link: Algorithmic Toolbox

These are Algorithmic Toolbox Week 6 Programming Assignment Coursera Answers

Programming Assignment 5: Dynamic Programming 1

6-1: Maximum Amount of Gold

def maximum_gold(capacity, weights):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i-1][w]
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w], dp[i-1][w - weights[i-1]] + weights[i-1])

    return dp[n][capacity]

if __name__ == '__main__':
    import sys
    input = sys.stdin.read
    data = list(map(int, input().split()))
    capacity = data[0]
    n = data[1]
    weights = data[2:]
    assert len(weights) == n

    print(maximum_gold(capacity, weights))

These are Algorithmic Toolbox Week 6 Programming Assignment Coursera Answers

6-2: Partitioning Souvenirs

from sys import stdin

def partition3(values):
    total_sum = sum(values)
    
    if total_sum % 3 != 0:
        return 0
    
    target_sum = total_sum // 3
    n = len(values)
    
    dp = [[[False] * (target_sum + 1) for _ in range(target_sum + 1)] for _ in range(n + 1)]
    dp[0][0][0] = True

    for i in range(1, n + 1):
        num = values[i - 1]
        for j in range(target_sum + 1):
            for k in range(target_sum + 1):
                dp[i][j][k] = dp[i-1][j][k]
                if j >= num:
                    dp[i][j][k] = dp[i][j][k] or dp[i-1][j-num][k]
                if k >= num:
                    dp[i][j][k] = dp[i][j][k] or dp[i-1][j][k-num]

    return 1 if dp[n][target_sum][target_sum] else 0

if __name__ == '__main__':
    input_n, *input_values = list(map(int, stdin.read().split()))
    assert input_n == len(input_values)
    print(partition3(input_values))

These are Algorithmic Toolbox Week 6 Programming Assignment Coursera Answers

6-3: Maximum Value of an Arithmetic Expression

def evaluate(a, b, op):
    if op == '+':
        return a + b
    elif op == '-':
        return a - b
    elif op == '*':
        return a * b
    else:
        assert False

def maximum_value(expression):
    digits = []
    operations = []

    for i in range(len(expression)):
        if i % 2 == 0:
            digits.append(int(expression[i]))
        else:
            operations.append(expression[i])

    n = len(digits)
    
    dp_min = [[0] * n for _ in range(n)]
    dp_max = [[0] * n for _ in range(n)]
    
    for i in range(n):
        dp_min[i][i] = digits[i]
        dp_max[i][i] = digits[i]
    
    for s in range(1, n):
        for i in range(n - s):
            j = i + s
            min_val = float('inf')
            max_val = float('-inf')
            for k in range(i, j):
                a = evaluate(dp_max[i][k], dp_max[k + 1][j], operations[k])
                b = evaluate(dp_max[i][k], dp_min[k + 1][j], operations[k])
                c = evaluate(dp_min[i][k], dp_max[k + 1][j], operations[k])
                d = evaluate(dp_min[i][k], dp_min[k + 1][j], operations[k])
                
                min_val = min(min_val, a, b, c, d)
                max_val = max(max_val, a, b, c, d)
            
            dp_min[i][j] = min_val
            dp_max[i][j] = max_val
    
    return dp_max[0][n - 1]

if __name__ == "__main__":
    import sys
    input_expression = sys.stdin.read().strip()
    print(maximum_value(input_expression))

These are Algorithmic Toolbox Week 6 Programming Assignment Coursera Answers

These are Algorithmic Toolbox Week 6 Programming Assignment Coursera Answers

Programming Assignment 5: Dynamic Programming 1

Similar: