動的計画法を使うのと使わないので実行時間がどれくらい変わるのかをpythonで検証してみた

## 動的計画法じゃなくて普通にナップサック問題を解く関数
def knapsack(cost, value, x):
  if len(cost) == 0 or x < 1: # P(0,x), P(i,0)のとき
    return 0,[] # 0と空リストを返す(空リストは最適解を返すときに使う)

  elif cost[-1] > x: # 物iの重みがxより大きいとき
    return knapsack(cost[:-1], value[:-1],x) # 物iは選ばないのでP(i-1,x)を返す

  else: # 物iの重みがx以下のとき
    ai = cost[-1] # 物iの重みにaiと名付ける
    ci = value[-1] # 物iの満足度にciと名付ける
    without_i, without_i_items = knapsack(cost[:-1],value[:-1],x) # 物iを選ばないとき:P(i-1,x)
    with_i, with_i_items = knapsack(cost[:-1], value[:-1], x-ai) # 物iを選ぶとき:P(i-1,x-ai)
    with_i += ci # 最適値にciを足す

    if with_i > without_i: # iを選ぶときの方がiを選ばないときより満足度が大きい場合
        return with_i, with_i_items+[len(cost) - 1] # P(i-1,x-ai)+ciを返す(with_i_itemsに物iのインデックスを追加)
    else: # iを選ばないときの方がiを選ぶときより満足度が大きい場合
        return without_i, without_i_items # P(i-1,x)を返す

## ナップサック問題を解く関数
def knapsack2(cost, value, x, memo=None):
    if memo is None: # メモを初期化する
        memo = {}

    if (len(cost), x) in memo: # メモがある場合はそれを返す
        return memo[(len(cost), x)]

    if len(cost) == 0 or x < 1: # P(0,x), P(i,0)のとき
        return 0, [] # 0と空リストを返す(空リストは最適解を返すときに使う)

    elif cost[-1] > x: # 物iの重みがxより大きいとき
        result = knapsack2(cost[:-1], value[:-1], x, memo) # 物iは選ばないのでP(i-1,x)をresultに格納
        memo[(len(cost), x)] = result # メモ化
        return memo[(len(cost),x)] # メモを返す
    
    else:  # 物iの重みがx以下のとき
        ai = cost[-1]  # 物iの重みにaiと名付ける
        ci = value[-1]  # 物iの満足度にciと名付ける
        without_i, without_i_items = knapsack2(cost[:-1], value[:-1], x, memo)  # 物iを選ばないとき:P(i-1,x)
        with_i, with_i_items = knapsack2(cost[:-1], value[:-1], x - ai, memo)  # 物iを選ぶとき:P(i-1,x-ai)
        with_i += ci  # 最適値にciを足す

        if with_i > without_i: # iを選ぶときの方がiを選ばないときより満足度が大きい場合
            result = with_i, with_i_items + [len(cost) - 1] # P(i-1,x-ai)+ciをresultに格納(with_i_itemsに物iのインデックスを追加)
        else: # iを選ばないときの方がiを選ぶときより満足度が大きい場合
            result = without_i, without_i_items # P(i-1,x)をresultに格納

        memo[(len(cost), x)] = result # メモ化
        return memo[len(cost),x]

import time # timeをインポートする
import random # randomをインポートする
random.seed(1) # ランダム値を固定

# コードの実行開始時刻を記録
start_time = time.time()

num = [5,10,15,20,25,30,35] # 要素数のリストを作成
result = [] # 結果を格納する空リストを作成
for n in num: 
# ナップサック問題のプログラムを実行
  C = [random.randint(1,8) for i in range(n)] # 重みをランダムにn個生成
  V = [random.randint(10,90) for i in range(n)] #満足度をランダムにn個生成
  X = n # 重量制限をnに設定
  knapsack(C,V,X) # ナップサック問題を解く

  # コードの実行終了時刻を記録
  end_time = time.time()

  # 実行時間を計算して表示
  execution_time = end_time - start_time # 実行時間の計算
  result.append(execution_time) # 結果をresultに格納
  print(f"実行時間（選択肢：{n}個）:", execution_time, "秒") # 実行時間の表示

import time # timeをインポートする
import random # randomをインポートする
random.seed(1) # ランダム値を固定

# コードの実行開始時刻を記録
start_time = time.time()

num = [5,10,15,20,25,30,35] # 要素数のリストを作成
result2 = [] # 結果を格納する空リストを作成
for n in num:
# ナップサック問題のプログラムを実行
  C = [random.randint(1,8) for i in range(n)] # 重みをランダムにn個生成
  V = [random.randint(10,90) for i in range(n)] #満足度をランダムにn個生成
  X = n # 重量制限をnに設定
  knapsack2(C,V,X) # ナップサック問題を解く

  # コードの実行終了時刻を記録
  end_time = time.time()

  # 実行時間を計算して表示
  execution_time = end_time - start_time # 実行時間の計算
  result2.append(execution_time) # 結果をresultに格納
  print(f"実行時間（選択肢：{n}個）:", execution_time, "秒") # 実行時間の表示

import matplotlib.pyplot as plt
plt.plot(num, result, marker = "o", color = "blue", alpha = 0.5, markersize = 10, label = "non-dp")
plt.plot(num, result2, marker = "o", color = "green", alpha = 0.5, markersize = 10, label = "dp")
plt.yscale("log")
plt.xlabel("Number of elements")
plt.ylabel("Execution time (log scale)")
plt.title("Comparison of execution time")
plt.legend()
plt.show()