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