0-1 배낭 문제

0-1 Knapsack Problem; 0/1 Knapsack Problem; 01 Knapsack Problem

무게(크기)가 한정된 가방이 있고, 넣을 수 있는 물건의 무게(크기)와 가격이 정해져 있을 때 어떤 물건을 버리고 어떤 물건을 넣어야 최대한의 이익을 얻을 수 있는가를 구하는 알고리즘

• 0-1 이라는 말은 물건을 쪼갤 수 없다는 뜻이다.
• 결국 10만큼의 가치가 있는 물건을 1/2만 쪼개서 넣는다고 5의 가치를 가질수 없음을 전제로 한다.