0-1-Rucksackproblem Codebeispiel

Aus ProgrammingWiki

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

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()

0-1-Rucksackproblem Codebeispiel

Suche