목록가방 문제 (1)

라이브러리는 도서관 아닌가요

Knapsack Algorithm 배낭 문제 정리

가정 최대 무게가 정해진 가방이 있다. 그리고 각기 다른 가치와 무게를 지닌 물건들이 있다. 이 물건들을 가방에 집어넣을 때, 가치가 최대가 되게끔 집어넣는 방법은 어떤 게 있을까? 방법 1. 가능한 모든 경우의 수를 다 세본다. (Brute-Force) 2. 가치가 가장 최대인 물건들만 우선적으로 집어 넣는다. 그리디 (Greedy) 3. DP(Dynamic Programming), 동적 계획법을 사용한다. 진행 3번을 살펴보도록 하고 다음과 같이 가정하자. i == 물건들의 번호이자 넣는 것이 허용되는 범위 (i=4이면, 1, 2, 3, 4번의 물건만 고려한다는 뜻) j == 견딜 수 있는 무게 (j=3이면, 가방 무게를 3으로 한정 짓는다는 뜻) (처음 이렇게 보면 상당히 추상적인데, 2중 for문..
자료구조, 알고리즘 2021. 10. 30. 02:45
이전 Prev 1 Next 다음