3. Dynamic programming

knapsack Problem

item 마다 weight 과 value가 있고, 정해진 weight limitation 하에 최적의 value를 구하는 문제.

모든 경우의 수를 다 따지려면 2의 n제곱 만큼의 time complexity가 필요하다.

 

 

dynamic programming은 문제를 나누어서 접근하는 방법으로 divide and conquere과도 비슷하다.

보통의 경우 lookup table을 두는데,

subproblem에 대한 solution들을 저장해 둔다.

추가 되는 경우의 수마다 최적값을 업데이트 해나가는데,,

내 생각에 이는 greedy 알고리즘과도 비슷하게 느껴졌다.

 

문제의 핵심은 problem을 subproblem으로 break down 할 수 있느냐는 부분.

 

def knapsack_max_value(knapsack_max_weight, items):
    
    # Initialize a lookup table to store the maximum value ($) 
    lookup_table = [0] * (knapsack_max_weight + 1)


    # Iterate down the given list
    for item in items:
        
        # The "capcacity" represents amount of remaining capacity (kg) of knapsack at a given moment. 
        for capacity in reversed(range(knapsack_max_weight + 1)):
            
            if item.weight <= capacity:
                lookup_table[capacity] = max(lookup_table[capacity], lookup_table[capacity - item.weight] + item.value)

    return lookup_table[-1]