Untitled

import numpy as np
import matplotlib.pyplot as plt


def knapsack(przedmioty, waga):
    n = len(przedmioty)
    T = np.zeros((n + 1, waga + 1))

    for i in range(1, n + 1):
        for j in range(waga + 1):
            p_wartosc, p_waga = przedmioty[i - 1]
            if p_waga < j:
                T[i, j] = max(T[i - 1, j], T[i - 1, j - p_waga] + p_wartosc)
            else:
                T[i, j] = T[i - 1, j]

    # wyswietlanie
    K = np.zeros((n + 1, waga + 1))
    for i in range(1, n + 1):
        for j in range(waga + 1):
            p_wartosc, p_waga = przedmioty[i - 1]
            if p_waga < j and T[i - 1, j] < T[i - 1, j - p_waga] + p_wartosc:
                K[i, j] = 1
            else:
                K[i, j] = 0

    for i in range(n + 1, 1):
        if K[i, j] == 1:
            print(i)
            j = j - p_waga

    return K[n, waga], T[n, waga]

#                P1       P2       P3       P4       P5      P6
przedmioty = [(12, 12), (5, 8), (9, 10), (10, 7), (6, 10), (7, 3)]

print("Wartość plecaka wynosi: ")
data = knapsack(przedmioty, 30)
print(knapsack(przedmioty, 30))

print(data)

# JAK WYDRUKOWAC TĄ LISTE PRZEDMIOTÓW (ILE JAKIEGO WZIĘTO)
print("Wzięto przedmioty:")

knapsack