0/1 배낭 문제

0/1 배낭 문제는 실제로 자원 배분, 물류, 투자 관리 등 다양한 현실 세계의 문제에서 응용될 수 있습니다. 특히, 한정된 자원 내에서 최대의 가치를 도출해야 하는 경우에 매우 적합하죠! 🤖

🧑‍🏫 문제 정의

• 아이템 수: N개
• 각 아이템: 가치 $v_i$와 무게 $w_i$를 가짐
• 배낭의 최대 수용 무게: W

🎯 목표

배낭에 넣을 수 있는 아이템을 선택하여 총 가치를 최대화하고, 배낭의 최대 무게를 넘지 않도록 하는 것입니다!
👉 하지만, 각 아이템은 0 또는 1번만 선택할 수 있다는 점을 기억하세요! (아이템은 부분적으로 나눌 수 없음)

🌟 해결 접근법: 동적 계획법(DP)

0/1 배낭 문제는 모든 가능한 조합을 탐색하는 건 비효율적입니다. 그래서 우리는 동적 계획법을 사용합니다! 🎉

⚙️ 동적 계획법 알고리즘

🔑 DP 테이블

• $K[i][w]$는 아이템 1부터 i까지 고려했을 때, 무게 w 이하의 배낭에 담을 수 있는 최대 가치를 저장합니다.
• 크기: $(N+1) \times (W+1)$

점화식

$K[i][w] = \begin{cases} 0 & \text{if } i = 0 \text{ or } w = 0 \\ K[i - 1][w] & \text{if } w_i > w \\ \max(K[i - 1][w], v_i + K[i - 1][w - w_i]) & \text{if } w_i \leq w \end{cases}$

🛠️ 알고리즘 단계

1. DP 테이블 초기화
2. 이중 루프를 사용하여 $i = 0$부터 $N$까지, $w = 0$부터 $W$까지 순회
3. 점화식 적용
4. 최종 결과: $K[N][W]$

🏆 예제 문제 적용

• 아이템 수 N: 3
• 최대 무게 W: 50
• 아이템 정보:

i	( v_i )	( w_i )
1	60	10
2	100	20
3	120	30

최종 결과:
아이템 2와 3을 선택하면 최대 가치는 220이 됩니다! 💰

💡 공간 최적화: 1차원 배열 사용

동적 계획법의 공간 복잡도를 줄이기 위해 1차원 배열을 사용할 수 있습니다.

• $K[w] = \max(K[w], v_i + K[w - w_i])$
• 이를 통해 공간 복잡도를 $O(W)$로 줄일 수 있습니다.

✨ 결론

0/1 배낭 문제는 DP를 통해 효율적으로 해결할 수 있는 클래식 최적화 문제입니다. 현실 문제에 응용 가능하며, 자원 배분이나 예산 관리 등의 다양한 분야에서 큰 도움을 줄 수 있습니다! 💪📊