[Algorithm] Knapsack

알고리즘 개념 특정 제한 조건 내에서 가장 높은 가치를 얻을 수 있는 선택 조합을 찾는 문제를 해결하기 위한 알고리즘즉, 조합 최적화 문제의 일종 배낭문제가 대표적 -  담을 수 있는 최대 무게가 정해진 배낭과 함께     각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때,     배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제  알고리즘 종류이때, 주어진 아이템의 분할 가능 여부에 따라 두 종류로 나뉜다.이번 블로그 글에서는 분할 불가한 0/1 Knapsack을 다룰 것이다.알고리즘 종류해결 방법특징(아이템 분할 여부) 0/1 Knapsack 동적 계획법, 백트레킹아이템 분할 불가  Fractional Knapsack 탐욕적 접근법아이템 분할 선택 가능 1..

2024.12.13