AuK/Dynamic Programming/0-1-Rucksackproblem Codebeispiel

Wiki-Quelltext dieser Seite.

<language>Python</language>
Das folgende Programm berechnet die Anzahl der Aufrufe für die Tabellenfelder am Beispiel von "Zufallsgegenständen". Der Einfluss von Memoizing ist sehr deutlich.

<code id="5f500266ca578">
import random as rnd
import matplotlib.pyplot as plt
from matplotlib.ticker import MaxNLocator
import numpy as np


def rand_items(n):
    items = []
    for i in range(0, n):
        items.append((rnd.randint(1, 100), rnd.randint(1, 100)))
    return items


calls_with_memo = []
calls_without_memo = []

for i in range(2, 21):
    calls1 = 0
    calls2 = 0
    
    for j in range(0, 5):
        K = 20 * i
        items = rand_items(i)
        n = len(items) - 1
        global weights
        weights = []
        global values
        values = []
        global calls
        calls = 0
        for item in items:
            weights.append(item[0])
            values.append(item[1])
        value_memo(n, K)
        calls1 += calls
        calls = 0
        value(n, K)
        calls2 += calls
        calls = 0
    calls_with_memo.append(calls1 / 5)
    calls_without_memo.append(calls2 / 5)
    
x = np.arange(2, 21)
y1 = np.asarray(calls_with_memo)
y2 = np.asarray(calls_without_memo)
    
fig = plt.figure(figsize=(11,8))
ax1 = fig.add_subplot(111)

ax1.plot(x, y1, label='Funktionsaufrufe mit Memoization')
ax1.plot(x, y2, label='Funktionsaufrufe ohne Memoization')
ax1.xaxis.set_major_locator(MaxNLocator(integer=True))

plt.legend()
plt.show()
</code>

[[Datei:Dynamic_programming_plot.png|450px]]