0-1 Knapsack Problem

0-1 Knapsack Problem

다이나믹 프로그래밍의 대표적인 문제라 할 수 있는 문제입니다.

무게 제한이 있는 배낭에 가치가 최대가 되도록 짐을 넣는 문제인데, 넣을 수 있는 짐을 쪼갤 수 있느냐 없느냐에 따라 ① 분할가능 배낭문제(Fractional Knapsack) ② 0-1 배낭문제(0-1 Knapsack problem) 으로 나눠집니다. 

 

분할가능 배낭문제는 Greedy 알고리즘을 활용하여 최적으로 풀이가 가능하지만 분할이 불가능한 0-1 배낭문제는 모든 경우의 수를 봐야합니다. 0-1 배낭문제를 최적화 하기 위해 다이나믹 프로그래밍, Tabulation이 활용됩니다. 

 

0-1 배낭문제에 (가치, 무게) 형태의 Tuple 이 저장된 리스트가 Input으로 들어온다고 하면, 아래와 같은 테이블을 구성하게 됩니다.  제한된 배낭의 무게가 현재 배낭의 무게보다 작은 경우에는 이전에 계산된 값을 그대로 쓰기 때문에 계산량을 매우 줄일 수 있습니다.

 

 

https://codingsarang.github.io/2020/07/01/algorithm/dp64/

Solution

def zero_one_knapsack(cargo):
    capacity = 5
    pack = []
    
    for i in range(len(cargo)+1):
        pack.append([]) #테이블 구성
        
        for c in range(capacity +1): #가로 capacity,세로 cargo 가 되는 테이블 구성
            # 이때 세로 cargo는 입력된 순서
            if i ==0 or c == 0 :
                pack[i].append(0)
            elif cargo[i-1][1] <= c : #입력된 cargo의 무게가 제약보다 작다면,
#                 print(cargo[i-1][0], pack[i-1][c-cargo[i-1][1]], c-cargo[i-1][1], c, cargo[i-1][1])
                pack[i].append(
                    max(
                        # 현재 cargo 가격 + (제약-현재 Cargo 무게)의 가격  
                        # 현재 Carago 가격 + 이전 Cargo 까지의 가격(테이블에서 제약-현재 cargo 무게 뺀 위치
                        cargo[i-1][0] + pack[i-1][c-cargo[i-1][1]],
 
                        pack[i-1][c] # 이전 가격 
                        
                    )
                )
            else :
                pack[i].append(pack[i-1][c])
#             print(pack)
    return pack[-1][-1]
cargo = [(4,12),(2,1),(10,4),(1,1),(2,2)]
zero_one_knapsack(cargo)