배낭 문제란? 배낭 문제는 조합 최적화 문제의 일종이다.
간략하게 말하자면, 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제이다. 우리가 흔히 쓰는 배낭 문제는 Fraction Knapsack Problem 0-1 Knapsack Problem 이 2가지가 존재한다.
Fraction Knapsack Problem (분할 가능한 배낭 문제) with Greedy Algorithm 내가 배낭 문제를 처음 접했을때 든 생각은 "어 이거 그리디 알고리즘 아닌가?" 였다.
그리디 알고리즘에서 가장 유명한 문제인 동전 거스름돈 문제는 일단 거스름돈으로 사용할 500원, 1.....
