🎒 배낭 문제
무게 제한 안에서
가장 값진 조합은?
배낭 무게 제한이 정해져 있어요. 아래 물건들 중 무게 합이 제한을 넘지 않으면서, 가치의 합이 최대가 되도록 골라보세요. 다 고른 다음 "최적 조합 보기"를 눌러 컴퓨터의 답과 비교해보세요.
왜 어려운 문제일까요? 물건이 n개면 가능한 조합은 2ⁿ가지나 돼요. 물건 30개만 돼도 10억 가지가 넘어서 전부 확인하기 힘들어요. 컴퓨터는 동적계획법(DP)이라는 똑똑한 방법으로 이 문제를 훨씬 빠르게 풀어요.
담은 무게 0/15kg
담은 가치 0
💡 배낭 문제는 택배 트럭에 짐 싣기, 예산 안에서 투자 종목 고르기처럼 "제한된 자원으로 최대 이득 뽑기" 문제 전체를 대표하는 유명한 최적화 문제예요.