aisd/Lab4/backpack.py

import random
import time
import matplotlib.pyplot as plt
import sys

def greedy(n, weight, value, capacity ):
    pairs = list(zip(value, weight))
    pairs.sort(reverse=True, key=lambda x: x[0] / x[1])

    current_value = 0
    currentCapacity = capacity

    for i in range(n):
        if pairs[i][1] <= currentCapacity:
            current_value += pairs[i][0]
            currentCapacity -= pairs[i][1]

    return current_value

def dynamic(n, weight, value, capacity, print_table=False):
    table = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weight[i - 1] <= w:
                table[i][w] = max(table[i - 1][w], table[i - 1][w - weight[i - 1]] + value[i - 1])
            else:
                table[i][w] = table[i - 1][w]


    if print_table:
        print("\n".join(["\t".join(map(str, row)) for row in table]))
    return table[n][capacity]

def benchmark_containers(container_list, capacity):
    greedy_times = []
    dynamic_times = []
    greedy_values = []
    dynamic_values = []
    rel_errors = []

    # For each container number or capacity
    for containers in container_list:
        weights = [random.randint(1, 10) for _ in range(containers)]
        values = [random.randint(1, 20) for _ in range(containers)]

        # Dynamic
        start = time.time()
        dyn = dynamic(containers, weights, values, capacity)
        dyn_time = (time.time() - start) * 1000

        # Greedy
        start = time.time()
        gr = greedy(containers, weights, values, capacity)
        gr_time = (time.time() - start) * 1000

        greedy_times.append(gr_time)
        dynamic_times.append(dyn_time)
        greedy_values.append(gr)
        dynamic_values.append(dyn)

        print(f"greedy: {gr}, dynamic: {dyn}, rel_error: {(dyn - gr) / dyn * 100 if dyn != 0 else 0:.2f}%")
        rel_errors.append((dyn - gr) / dyn * 100 if dyn != 0 else 0)

    return greedy_times, dynamic_times, rel_errors

def benchmark_capacity(capacity_list, containers):
    greedy_times = []
    dynamic_times = []
    greedy_values = []
    dynamic_values = []
    rel_errors = []

    # For each container number or capacity
    for capacity in capacity_list:
        weights = [random.randint(1, 10) for _ in range(containers)]
        values = [random.randint(2, 20) for _ in range(containers)]

        # Dynamic
        start = time.time()
        dyn = dynamic(containers, weights, values, capacity)
        dyn_time = (time.time() - start) * 1000

        # Greedy
        start = time.time()
        gr = greedy(containers, weights, values, capacity)
        gr_time = (time.time() - start) * 1000

        greedy_times.append(gr_time)
        dynamic_times.append(dyn_time)
        greedy_values.append(gr)
        dynamic_values.append(dyn)
        print(f"greedy: {gr}, dynamic: {dyn}, rel_error: {(dyn - gr) / dyn * 100 if dyn != 0 else 0:.2f}%")

        rel_errors.append((dyn - gr) / dyn * 100 if dyn != 0 else 0)

    return greedy_times, dynamic_times, rel_errors

if __name__ == "__main__":
    # Check if there was given a second argument, if yes run a test instead of the benchmark
    if len(sys.argv) > 1:
        file = sys.argv[1]
        """
        Format we are expecting:
        5 - liczba elementów
        3 2 4 3 1 - rozmiary
        5 3 4 4 2 - wartości
        8 - rozmiar plecaka
        """
        with open(file, 'r') as f:
            lines = f.readlines()
            n = int(lines[0].strip())
            weights = list(map(int, lines[1].strip().split()))
            values = list(map(int, lines[2].strip().split()))
            capacity = int(lines[3].strip())

            dynamic(n, weights, values, capacity, print_table=True)
            print(greedy(n, weights, values, capacity))
        exit(0)

    # First test case - constant capacity, variable number of containers
    containers_list = list(range(1, 51, 2))

    # Constant capacity of 20
    greedy_times, dynamic_times, rel_errors = benchmark_containers(containers_list, 20)

    plt.figure(figsize=(12,5))
    plt.subplot(1,2,1)
    plt.plot(containers_list, greedy_times, label='Zachłanny', )
    plt.plot(containers_list, dynamic_times, label='Dynamiczny', )
    plt.xlabel('Liczba kontenerów')
    plt.ylabel('Czas [ms]')
    # plt.yscale('log', base=2)
    plt.title('Czas działania dla zmiennej liczby kontenerów (B=20)')
    plt.legend()

    axis = plt.subplot(1,2,2)
    plt.bar(containers_list, rel_errors)
    plt.xlabel('Liczba kontenerów')
    plt.ylabel('Błąd względny [%]')
    axis.yaxis.set_major_formatter(lambda x, pos: f'{x}%'.replace('.0', ''))
    plt.title('Błąd względny')
    plt.savefig('benchmark_vary_n.png')


    # Second test case - variable capacity, constant number of containers
    capacity_list = list(range(5, 101, 5))

    # Constant number of containers of 50
    greedy_times, dynamic_times, rel_errors = benchmark_capacity(capacity_list, 50)

    plt.figure(figsize=(12,5))
    plt.subplot(1,2,1)
    plt.plot(capacity_list, greedy_times, label='Zachłanny' )
    plt.plot(capacity_list, dynamic_times, label='Dynamiczny')
    plt.xlabel('Pojemność')
    plt.ylabel('Czas [ms]')
    plt.title('Czas działania dla zmiennej pojemności (n=50)')
    plt.legend()

    axis =  plt.subplot(1,2,2)
    plt.bar(capacity_list, rel_errors )
    plt.xlabel('Pojemność')
    plt.ylabel('Błąd względny [%]')
    axis.yaxis.set_major_formatter(lambda x, pos: f'{x}%'.replace('.0', ''))
    plt.title('Błąd względny')
    plt.savefig('benchmark_vary_capacity.png')