import random
import time


def knapsack_brute_force(weights, values, capacity, i):
    if capacity == 0 or i == 0:
        return 0
    if weights[i] > capacity:
        return knapsack_brute_force(weights, values, capacity, i - 1)
    else:
        return max(knapsack_brute_force(weights, values, capacity, i - 1),
                   values[i] + knapsack_brute_force(weights, values, capacity - weights[i], i - 1))


def knapsack_dp(weights, values, capacity, i, memo=None):
    if memo is None:
        memo = {}
    if (capacity, i) in memo:
        return memo[(capacity, i)]
    if capacity == 0 or i == 0:
        return 0
    if weights[i] > capacity:
        memo[(capacity, i)] = knapsack_dp(weights, values, capacity, i - 1, memo)
        return memo[(capacity, i)]
    else:
        memo[(capacity, i)] = max(knapsack_dp(weights, values, capacity, i - 1, memo),
                                  values[i] + knapsack_dp(weights, values, capacity - weights[i], i - 1, memo))
        return memo[(capacity, i)]


def run(n, capacity):
    weights = [random.randint(1, 10) for _ in range(n)]
    values = [random.randint(1, 10) for _ in range(n)]

    brute_force_start = time.time()
    value = knapsack_brute_force(weights, values, capacity, len(weights) - 1)
    brute_force_time = time.time() - brute_force_start
    print("Without dynamic programming times: ", brute_force_time, " Value: ", value)

    dp_start = time.time()
    value = knapsack_dp(weights, values, capacity, len(weights) - 1)
    dp_time = time.time() - dp_start
    print("With dynamic programming times: ", dp_time, " Value: ", value)


if __name__ == '__main__':
    run(50, 25)