Algorithm/알고리즘 개념

설명 배낭 문제(Knapsack Problem)는 조합 최적화의 유명한 문제다. 예를 들어 설명해보자. 한 여행가가 여행을 떠나려고 한다. 여행가가 가지고 가는 배낭에는 담을 수 있는 무게의 최댓값이 정해져 있고 배낭에 넣을 수 있는 짐에는 각각의 무게(W)와 가치(V)가 정해져 있다. 이 여행가가 배낭의 무게를 최대한 꽉 채우되 가치의 합이 최대가 되도록 짐을 고르려면 어떻게 해야 할까? 여기서 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우 두 가지로 나눌 수 있다. 짐을 쪼갤 수 있는 분할 가능 배낭 문제(Fractional Knapsack Problem) - 그리디 알고리즘 짐을 쪼갤 수 없는 배낭 문제(Knapsack Problem) - 동적 계획법(Dynami..