[알고리즘] 배낭 채우기 알고리즘(Knapsack Problem)

Knapsack 문제와 Python으로의 구현

Knapsack 문제는 최적화 문제로 알려져 있으며, 가장 잘 알려진 결정론적 알고리즘 문제 중 하나입니다. 다양한 변형이 있지만, 여기서는 가장 대표적인 0-1 knapsack 문제에 대해 설명하겠습니다.

 

문제 설명: 주어진 물건들과 각 물건의 가치 및 무게, 그리고 일정한 무게를 수용할 수 있는 가방이 있을 때, 가방에 넣을 수 있는 물건들의 가치의 합을 최대화하는 문제입니다.

수식으로 표현하면:

• n개의 물건이 있고, i번째 물건의 무게는 w[i], 가치는 v[i]라 하자.
• 가방의 최대 무게는 W로 한정되어 있다.
• dp[i][j]를 i번째 물건까지 고려하고 가방의 무게 한도가 j일 때의 최대 가치로 정의한다.

본 문제를 풀기 위한 점화식:

def knapsack(W, w, v, n):
    # DP 테이블 초기화
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]

    # 점화식을 이용한 계산
    for i in range(n + 1):
        for j in range(W + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif w[i-1] <= j:
                dp[i][j] = max(v[i-1] + dp[i-1][j-w[i-1]], dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]

    return dp[n][W]

# 예제
values = [60, 100, 120]
weights = [10, 20, 30]
W = 50
n = len(values)
print(knapsack(W, weights, values, n))  # 출력: 220

 

예시문제

https://www.acmicpc.net/problem/7579

7579번: 앱

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭