DP(동적 계획법, Dynamic Programming ) - 배낭 문제

 

1. 0/1 배낭 문제 (0/1 Knapsack)

• 물건을 한 번만 선택할 수 있는 배낭 문제입니다.
• 대표적인 DP 유형 문제로, "물건을 넣을지 말지" 를 결정해야 합니다.
• 점화식 예시: dp[i][w]=max⁡(dp[i−1][w],dp[i−1][w−weight[i]]+value[i])dp[i][w] = \max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])
• 추천 문제:
  • 백준 12865번 - 평범한 배낭 (기본적인 0/1 Knapsack)

---

2. 분할 가능 배낭 문제 (Fractional Knapsack)

• 물건을 부분적으로 쪼개서 넣을 수 있는 문제입니다.
• 그리디 알고리즘을 사용하여, 단위 가치(가치/무게)가 높은 순서대로 선택하면 됩니다.
• 추천 문제:
  • 백준 11047번 - 동전 0 (배낭 문제는 아니지만, 그리디 연습에 적합)

---

3. 무제한 배낭 문제 (Unbounded Knapsack)

• 같은 물건을 여러 번 선택할 수 있는 배낭 문제입니다.
• 점화식에서 dp[i-1] 대신 dp[i]를 사용해 물건을 중복해서 사용할 수 있도록 합니다.
• 점화식 예시: dp[w]=max⁡(dp[w],dp[w−weight[i]]+value[i])dp[w] = \max(dp[w], dp[w - weight[i]] + value[i])
• 추천 문제:
  • 백준 2293번 - 동전 1
  • 백준 2294번 - 동전 2

---

4. 다중 배낭 문제 (Bounded Knapsack)

• 같은 물건을 여러 개 가질 수 있지만, 개수 제한이 있는 경우입니다.
• 이진법을 활용한 "Binary Optimization" 기법을 사용해 해결할 수 있습니다.
• 추천 문제:
  • 백준 12920번 - 평범한 배낭 2

---

5. 배낭 문제와 경로 탐색이 결합된 문제

• 배낭 문제의 원리를 응용해서 최적의 경로를 찾는 문제들이 있습니다.
• 추천 문제:
  • 백준 14863번 - 서울에서 경산까지
  • 백준 7579번 - 앱

---

6. 다차원 배낭 문제 (Multi-dimensional Knapsack)

• 물건마다 여러 개의 제약 조건이 있는 경우입니다.
• 예를 들어, 무게뿐만 아니라 용량 같은 추가적인 조건이 있을 수 있습니다.
• 추천 문제:
  • 백준 16493번 - 최대 페이지 수

---

7. 부분배낭 문제 (Subset Sum)

• 배낭 문제에서 가치(value)가 없고, 특정 무게를 만들 수 있는지를 묻는 문제입니다.
• 추천 문제:
  • 백준 1450번 - 냅색문제

---