배낭 문제(Knapsack Problem)

배낭 문제(Knapsack Problem)

• 배낭 문제(Knapsack Problem) 는 조합 최적화 문제 중 하나로, 주어진 제한된 자원을 활용하여 최대의 가치를 얻는 방법을 찾는 문제입니다.

---

문제 설명

• 어떤 배낭이 담을 수 있는 최대 무게(Capacity) 가 있을 때, 각각의 아이템 은 고유한 무게(Weight) 와 가치(Value) 를 가집니다.
• 이때 배낭에 넣을 수 있는 아이템의 조합 중 가치의 합이 최대가 되는 조합을 찾는 것이 목표입니다.`

---

문제 유형

• 1. 0/1 배낭 문제 (0/1 Knapsack Problem):
  • 각 아이템은 하나씩만 선택 가능.
  • 선택(1)하거나 선택하지 않음(0).
• 2. 분수 배낭 문제 (Fractional Knapsack Problem):
  • 아이템의 일부를 나눠 배낭에 넣을 수 있음.
  • 탐욕 알고리즘(greedy approach)으로 해결 가능.

---

수학적 정의

• n개의 아이템: 무게 , 가치
• 최대 배낭 용량:
• 목표: 다음을 최대화 [ ]
  • 제약 조건: [ ]
  • 여기서 는 아이템 를 선택하면 , 선택하지 않으면 .

---

해결 방법

1. 동적 계획법 (Dynamic Programming)

• 0/1 배낭 문제에 적합.

• 시간 복잡도: : 아이템 수, : 배낭 용량)

• DP 테이블:

  • : 번째 아이템까지 고려했을 때 용량 에서 얻을 수 있는 최대 가치.

• 점화식:

  [

  (아이템 i를 선택하지 않는 경우)

  (아이템 i를 선택하는 경우) ]

2. 분지 한정법 (Branch and Bound)

• 최적화된 탐색을 통해 불필요한 계산을 줄임.
• 사용 사례: 문제의 입력 크기가 큰 경우.

3. 탐욕 알고리즘 (Greedy Algorithm)

• 분수 배낭 문제 에 적합.
• 각 아이템의 가치 대비 무게 비율 기준으로 정렬 후, 가능한 만큼 배낭에 넣음.

---

예제

입력

• 아이템 :
  (가치),
  (무게)
• 배낭 용량 :

출력

0/1 배낭 문제: 최대 가치 = 220
분수 배낭 문제: 최대 가치 = 240

---

파이썬 코드 (동적 계획법)

python

def knapsack(weights, values, capacity):
    n = len(values)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
    
    return dp[n][capacity]

weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
print(knapsack(weights, values, capacity))  # 출력: 220

---

특징

• 0/1 배낭 문제는 동적 계획법이 적합하지만, 입력 크기가 매우 크면 효율적으로 해결하기 어렵습니다.
• 분수 배낭 문제는 탐욕 알고리즘으로 빠르게 해결 가능합니다.

view raw Knapsack.ko.md hosted with ❤ by GitHub