0/1 배낭 문제

보통

0/1 Knapsack

한정된 배낭에 무엇을 넣어야 가장 비쌀까요?

📊 복잡도

구분	복잡도
최선	O(n * W)
평균	O(n * W)
최악	O(n * W)
공간	O(n * W)

🏷️ 태그

DP2D 테이블최적화

📖 개념 소개

배낭 크기는 한정되어 있는데, 담고 싶은 물건은 많습니다. "어떤 물건들을 골라야" 배낭 안 물건들의 가치 합이 최대가 될까요? 이것을 해결하는 방법입니다.

1/64

🎯상황 설명

가방에 물건을 담아 최대 가치를 얻고 싶어요! • 가방 최대 용량: 7kg • 물건 4개: 🎸Guitar, 💻Laptop, ⛺Tent, 🏆Gold • 각 물건은 "넣거나(1)" 또는 "안 넣거나(0)" 둘 중 하나! (반으로 쪼개서 넣기 불가 → "0/1" 배낭 문제)

🔒

0/1 배낭 문제

보통

0/1 Knapsack

한정된 배낭에 무엇을 넣어야 가장 비쌀까요?

📊 복잡도

구분	복잡도
최선	O(n * W)
평균	O(n * W)
최악	O(n * W)
공간	O(n * W)

🏷️ 태그

DP2D 테이블최적화

📖 개념 소개

1/64

🎯상황 설명

🔒

🎯상황 설명

0/1 배낭 문제

정의

핵심 특성

시간 복잡도

🎯상황 설명

0/1 배낭 문제

정의

핵심 특성

시간 복잡도