Algorithm | 0-1 Knapsack

0-1 Knapsack 문제는 DP를 공부하다 보면 꼭 한 번은 마주치게 되는 문제다.
나 역시 풀 때마다 DP 테이블을 어떻게 구성해야 할지 헷갈려서, 이번 기회에 개념을 정리해두기로 했다.
GPT-4o의 도움도 받아가며, 내 방식대로 정리해본 글이다.

---

0-1 Knapsack 문제의 특징 ✅

1. 아이템이 각각 하나씩만 선택 가능

• 아이템은 중복해서 사용할 수 없다.
• 즉, 한 아이템을 넣거나(1), 안 넣거나(0) 두 선택지만 존재한다.

→ "이 아이템을 선택할까 말까?" 의사결정만 존재함

---

2. 무게 제한이 존재

• 어떤 총량(보통 무게)의 제한이 존재하고,
• 이 범위 내에서 최대 가치를 구하는 문제.

→ "이 아이템들을 제한된 무게 안에 어떻게 담을까?"가 핵심

---

3. 목표가 보통 ‘최대 가치’ 또는 ‘최대 효율’

• 예: 제한된 공간(무게) 안에서 얻을 수 있는 최대의 이익/가치

---

4. 아이템 개수와 최대 무게가 주어진다

• 보통 입력으로 n개 아이템, 최대 무게 W 형태.

---

0-1 Knapsack이 아닌 경우 ❌

1. 무제한 선택 가능 → Unbounded Knapsack

• 예: “동전을 무한히 사용해 목표 금액을 맞춰라” 같은 문제

2. 물건을 쪼갤 수 있음 → Fractional Knapsack

• 예: “이 물건을 반만 넣어도 된다” → 그리디 방식으로 해결됨

3. 단순 조합 문제이지만 무게 개념이 없음

• 예: “합이 어떤 수가 되도록 부분집합을 선택하라”

  → Subset Sum Problem으로 분류될 수 있음 (사촌 문제임)

---

내가 쓰는 직관적 체크리스트 🎯

체크 항목	예/아니오
아이템마다 1번만 선택 가능한가?	✅
무게(또는 용량) 제한이 있는가?	✅
목표가 최대 가치(또는 이익)인가?	✅
아이템 수와 무게 제한이 명시되어 있는가?	✅

이 네 가지가 모두 ‘예’라면, 거의 확실하게 0-1 Knapsack이다.

결론적으로, 문제를 보면 먼저 “아이템마다 선택이 0 또는 1인가?”를 묻고, 그다음 “무게 제한 + 최대 가치 구조인가?”를 확인하면 된다. 이 두 가지가 동시에 충족되면, 거의 무조건 0-1 Knapsack이라 생각하면 틀리지 않는다.

---

0-1 Knapsack 테이블을 만드는 팁 ❓

0-1 Knapsack 문제에서 DP 테이블을 작성하는 건 핵심 구현 중 하나다. 처음에는 복잡해 보이지만, 몇 가지 팁만 기억하면 훨씬 명확하게 짤 수 있다. 아래는 내가 테이블을 작성할 때 주로 따르는 기준들이다.

1. DP 테이블의 의미를 명확히 정리할 것

가장 중요한 건 “DP 테이블이 무엇을 의미하는가?”를 명시적으로 정의하는 것이다.

보통은 다음과 같이 정의한다:

dp[i][w]: 물건 i까지 고려했을 때, 무게 한도 w로 가질 수 있는 최대 가치

이 정의만 잘 기억하면, 이후 상태 전이도 자연스럽게 따라온다.

---

2. 테이블 크기 설계하기

• 아이템 개수가 n, 최대 무게가 W일 때, 테이블 크기는 dp[n+1][W+1]로 한다.
• i = 0이나 w = 0은 물건이 없거나 무게가 0인 경우로 해석되므로 기저 상태로 쓰인다.

---

3. 점화식 세우기

물건 i를 선택할 수 있을 때와 아닐 때를 나눠서 생각한다:

if w >= weight[i-1]:
    dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i-1]] + value[i-1])
else:
    dp[i][w] = dp[i-1][w]

• i-1을 쓰는 이유는 dp에서 i번째 줄은 i번째 아이템을 고려한다는 의미이고, 실제로는 0-based index로 되어 있기 때문.
• 물건을 안 넣는 경우: dp[i-1][w]
• 물건을 넣는 경우: dp[i-1][w - weight] + value

---

4. Pseudo-code 예시

for i from 1 to n:
    for w from 0 to W:
        if weight[i-1] <= w:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i-1]] + value[i-1])
        else:
            dp[i][w] = dp[i-1][w]

---

5. 기저 상태 초기화

• dp[0][w] = 0 for all w

• dp[i][0] = 0 for all i

  (물건이 없거나 무게가 0일 때 가치는 당연히 0)

---

6. 디버깅 팁

• 작은 데이터셋(예: 아이템 3개, 무게 6 이하)으로 먼저 테이블 출력해 보기
• dp 테이블 출력하면서, 어떤 선택이 어떤 값을 유도했는지 주석 달아보기

---

7. 1차원 배열로 최적화도 가능

• 위 테이블을 기반으로, 뒤에서 앞으로 순회하면 1차원 배열로도 구현 가능하다.
• 단, 이건 테이블 구조가 익숙해진 다음 최적화 용도로 쓰는 게 좋다.

예제 문제 🎒

• 아이템 3개
  • 무게: [1, 2, 3]
  • 가치: [6, 10, 12]
• 최대 허용 무게: W = 5

---

테이블 정의

dp[i][w] = 아이템 i개까지 고려했을 때, 무게 제한 w로 얻을 수 있는 최대 가치

• 테이블 크기: dp[4][6] (0부터 포함하므로 아이템 03개, 무게 05)

초기 상태

i \ w	0	1	2	3	4	5
0	0	0	0	0	0	0

---

테이블 채우기

i = 1 (아이템 1개, 무게 1, 가치 6)

i \ w	0	1	2	3	4	5
1	0	6	6	6	6	6

i = 2 (아이템 2개, 무게 2, 가치 10)

i \ w	0	1	2	3	4	5
2	0	6	10	16	16	16

• 예: dp[2][3]

  → 아이템 2(무게2, 가치10) 포함 시: dp[1][1] + 10 = 6 + 10 = 16

  → 포함하지 않으면 dp[1][3] = 6 → max는 16

i = 3 (아이템 3개, 무게 3, 가치 12)

i \ w	0	1	2	3	4	5
3	0	6	10	16	18	22

• 예: dp[3][5]

  → 아이템 3(무게3, 가치12) 포함 시: dp[2][2] + 12 = 10 + 12 = 22

  → 포함하지 않으면 dp[2][5] = 16 → max는 22

---

최종 테이블

i \ w	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	6	6	6	6	6
2	0	6	10	16	16	16
3	0	6	10	16	18	22

---

결론

• 최대 가치: dp[3][5] = 22
• 선택된 아이템: 아이템 2 (무게2, 가치10), 아이템 3 (무게3, 가치12) → 총 무게 5

이렇게 작게 만들어보면, 점화식과 테이블이 머리에 훨씬 잘 들어온다.

처음엔 항상 작은 테이블부터 연습하는 것이, 디버깅이나 로직 이해에 정말 도움이 많이 됐다.