배낭 문제 (그리디 알고리즘, 다이나믹 프로그래밍)

🗂 배낭 문제

배낭에 담을 수 있는 무게의 최대값이 15kg,
짐의 값과 무게가 각각 cargo = [(4, 12), (2, 1), (10, 4), (1, 1), (2, 2)] 일 때,
배낭에 담을 수 있는 짐 가격의 합의 최대값을 return

📌 배낭 문제 (짐을 1kg 단위로 쪼갤 수 있는 경우_ 그리디 알고리즘 사용)

def knapsack(cargo):
    capacity = 15 #배낭 용량
    #단가(1kg당 가격)가 높은 순으로 정렬
    cargo.sort(key = lambda x: (x[0] / x[1]), reverse = True)
    
    total_value = 0
    for c in cargo:
        if c[1] <= capacity:
            capacity -= c[1]
            total_value += c[0]
        else: #짐의 무게가 남은 용량보다 클 때
            #1kg단위로 쪼갠 가격을 남은 용량만큼 곱해서 더함
            total_value += capacity * (c[0] / c[1])
            break

    return total_value

if __name__ == '__main__':
    cargo = [(4, 12), (2, 1), (10, 4), (1, 1), (2, 2)]  #(가격, 무게)
    print('최대 가격: ', knapsack(cargo))  #최대 가격:  17.333333333333332

📌 배낭 문제 (짐을 1kg 단위로 쪼갤 수 없는 경우_ 다이나믹 프로그래밍 기법 사용)

def knapsack(cargo):
    capacity = 15 #배낭 용량
    pack = []  #pack[짐의 개수][배낭 용량]

    for i in range(len(cargo) + 1): #짐의 개수 : 0개 ~len(cargo)개
        pack.append([])
        for c in range(capacity + 1): #배낭 용량 : 0kg ~ capacity
            if i == 0 or c == 0: #짐의 개수 or 배낭 용량이 0 일 경우
                pack[i].append(0)
            elif cargo[i - 1][1] <= c: #새로 추가 된 짐의 무게가 배낭 용량 이하 일 경우 => 새로운 조합 가능
                pack[i].append(
                    max(
                        #새로 추가 된 짐 가격 + 짐이 추가 되기 전, 배낭 용량이 (현재 배낭 용량 - 새로 추가 된 짐 무게)의 값
                        cargo[i - 1][0] + pack[i - 1][c - cargo[i - 1][1]], 
                        #짐이 추가 되기 전 가격
                        pack[i - 1][c]
                    )
                )
            else: #새로 추가 된 짐의 무게가 배낭 용량보다 클 경우 => 새로운 조합 불가능
                pack[i].append(pack[i - 1][c])

    return pack[-1][-1]

if __name__ == '__main__':
    cargo = [(4, 12), (2, 1), (10, 4), (1, 1), (2, 2)]  #(가격, 무게)
    print('최대 가격: ', knapsack(cargo))  #최대 가격:  15