デフォルトのコード

def fib(n):

    if(n==0):

        return 0 #F(0)=0

    if(n==1):

        return 1 #F(1)=1

    return fib(n-1)+fib(n-2) #F(n)=F(n-1)+F(n-2)



print(fib(10))

デフォルトのコード

def fib_DP(n,memo={}):

    if n in memo:

        return memo[n]
    if(n==0):

        return 0 #F(0)=0

    if(n==1):

        return 1 #F(1)=1

    

    memo[n]=fib_DP(n-1,memo)+fib_DP(n-2,memo)

    return memo[n]


print(fib_DP(10))

デフォルトのコード

import timeit



#動的計画法なし

def fib(n):

    if(n==0):

        return 0 #F(0)=0

    if(n==1):

        return 1 #F(1)=1

    return fib(n-1)+fib(n-2) #F(n)=F(n-1)+F(n-2)





# 動的計画法あり

def fib_DP(n,memo={}):

    if n in memo:

        return memo[n]
    if(n==0):

        return 0 #F(0)=0

    if(n==1):

        return 1 #F(1)=1

    

    memo[n]=fib_DP(n-1,memo)+fib_DP(n-2,memo)

    return memo[n]
#第n項

ns = [5, 20, 35]


results = []


# 各nに対して実行時間を計測

for n in ns:

    fib_result = fib(n)

    fib_DP_result = fib_DP(n, {})

    # 実行時間を計測

    original_time = timeit.timeit('fib(n)', globals=globals(), number=1)

    memoized_time = timeit.timeit('fib_DP(n)', globals=globals(), number=1)



    results.append((n, fib_result, original_time, fib_DP_result, memoized_time))



# 結果を出力

for result in results:

    n, fib_result, original_time, fib_DP_result, memoized_time = result

    print(f"n = {n}")

    print(f"動的計画法なし: 解 {fib_result}  実行時間 {original_time:.6f} s")

    print(f"動的計画法あり: 解 {fib_DP_result}  実行時間 {memoized_time:.6f} s")

    print() 

デフォルトのコード

import time

def unbounded_knapsack(capacity, weights, values, n):

    # ベースケース：容量が0の場合

    if capacity == 0:

        return 0



    # 最大価値を保持する変数

    max_value = 0



    # すべてのアイテムについて繰り返す

    for i in range(n):

        # アイテムが容量内に収まる場合

        if weights[i] <= capacity:

            # そのアイテムを選んで再帰的に解く

            value_with_item = values[i] + unbounded_knapsack(capacity - weights[i], weights, values, n)

            # 最大価値を更新

            max_value = max(max_value, value_with_item)



    return max_value



# アイテムの重さと価値

weights = [5, 12,15,20,21]
values = [3,10,13,18,20]
# ナップサックの容量

capacity = 50

# アイテムの数

n = len(values)



#開始時間を記録

start_time=time.time()



# 最大価値を計算する

max_value = unbounded_knapsack(capacity, weights, values, n)



#終了時間を記録

end_time=time.time()

# 実行時間を計算

exec_time = end_time - start_time

print(f"ナップサックの最大価値: {max_value}")

print(f"実行時間: {exec_time:.6f} 秒")

デフォルトのコード

import time



def unbounded_knapsack_dp(capacity, weights, values):

    n = len(weights)

    dp = [0] * (capacity + 1)



    # 開始時刻を記録

    start_time = time.time()



    for c in range(capacity + 1):

        for i in range(n):

            if weights[i] <= c:

                dp[c] = max(dp[c], values[i] + dp[c - weights[i]])



    # 終了時刻を記録

    end_time = time.time()



    # 実行時間を計算

    execution_time = end_time - start_time



    return dp[capacity], execution_time



# アイテムの重さと価値

weights = [5, 12,15,20,21]
values = [3,10,13,18,20]
# ナップサックの容量

capacity = 50



# 最大価値と実行時間を取得

max_value, exec_time = unbounded_knapsack_dp(capacity, weights, values)

print(f"ナップサックの最大価値: {max_value}")

print(f"実行時間: {exec_time:.6f} 秒")

デフォルトのコード

import time



# アイテムの重さと価値

weights = [5, 12, 15, 20, 21]
values = [3, 10, 13, 18, 20]


def unbounded_knapsack(capacity, weights, values, n):

    # ベースケース：容量が0の場合

    if capacity == 0:

        return 0

    max_value = 0

    for i in range(n):

        if weights[i] <= capacity:

            value_with_item = values[i] + unbounded_knapsack(capacity - weights[i], weights, values, n)

            max_value = max(max_value, value_with_item)

    return max_value



def dp_knapsack(capacity, weights, values):

    n = len(weights)

    dp = [0] * (capacity + 1)

    start_time = time.time()

    for c in range(capacity + 1):

        for i in range(n):

            if weights[i] <= c:

                dp[c] = max(dp[c], values[i] + dp[c - weights[i]])

    end_time = time.time()

    execution_time = end_time - start_time

    return dp[capacity], execution_time



capacities = [50, 100, 130]


for capacity in capacities:

    # 再帰的アプローチの実行時間計測

    start_time = time.time()

    max_value_recursive = unbounded_knapsack(capacity, weights, values, len(values))

    end_time = time.time()

    exec_time_recursive = end_time - start_time



    # DPアプローチの実行時間計測

    max_value_dp, exec_time_dp = dp_knapsack(capacity, weights, values)



    # 結果の表示

    print(f"容量: {capacity}")

    print(f"DPなしナップサックの最大価値: {max_value_recursive}")

    print(f"DPなしの実行時間: {exec_time_recursive:.6f} 秒")

    print(f"動的計画法のナップサックの最大価値: {max_value_dp}")

    print(f"動的計画法の実行時間: {exec_time_dp:.6f} 秒")

    print("-------")