목록배낭문제 (1)

minkylee

[DP] 배낭 문제 (knapsack Problem)

조합 최적화 문제의 일종, 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제이다. 분할 가능한 배낭 문제 아이템들을 분할해서 담는 것이 가능하다 -> 단위 무게당 가치 순으로 높은 것들부터 담는 그리디 알고리즘 사용하면 됨 0-1 배낭문제 아이템들을 분할해서 담는 것이 불가능 그리디 알고리즘으로는 최적해를 찾을 수 없다. 동적 계획법, 백트래킹 등의 조합 최적화 문제의 풀이 방법으로 풀어야 한다. 대표적인 DP 알고리즘 중 하나. DP란, 큰 문제를 작은 문제로 나누어서 푸는 방법을 일컫는 말이다. 작은 부분의 답이 큰 부분의 답이 되고 이 부분들의 답이 전체의 ..
CSE/컴퓨터알고리즘 2024. 4. 16. 13:27
이전 Prev 1 Next 다음