📌 배낭문제(Knapsack Problem)란?

조합 최적화 문제의 일종. 주어진 물건(아이템)들을 “배낭”에 담을 때 담을 수 있는 물건들의 가치(Value) 합을 최대화하는 방법을 찾는 문제

대표유형으로는,

1. 0/1 배낭 문제(0/1 Knapsack Problem)
2. 분할 가능한 배낭 문제(Fractional Knapsack Problem)

📕 0/1 배낭 문제(0/1 Knapsack Problem)

• n개의 아이템이 있고, 각 아이템 i는 무게 wi와 가치 vi를 가짐.

• 배낭의 최대 허용 무게(용량)은 W

• 각 아이템은 0번(담지 않음) 또는 1번(담음) 담을 수 있음.

• 테이블(표)를 이용하는 DP로 문제를 풀 수 있음.

• DP 테이블 DP[i][w]: 아이템 1부터 i까지 고려했을 때, 배낭 용량이 w일 때 얻을 수 있는 최대 가치

• 시간 복잡도는 O(nW)

📕 누적합 알고리즘의 활용

• 분할 가능한 경우에는 그리디(Greedy) 알고리즘으로 최적해

• 아이템들을 단위 무게당 가치(
  가 큰 순으로 정렬

• 가장 효율(단위 무게당 가치)이 높은 아이템부터 가득 채우고, 용량이 남으면 그 다음으로 효율이 높은 아이템을 일부만 담는 식으로 진행

• 이 경우, 담을 수 있는 아이템이 남아 있으면 배낭 용량이 찰 때까지 계속 담으면 됨.

✒️ 예시문제

평범한 배낭
평범한 배낭 2
동전
함께 블록 쌓기