동적 계획법1 동적 계획법과 Knapsack 문제 🗯️ knapsack 문제 가능한 조합의 최적의 경우를 찾는 문제입니다. 배낭이 주어지고 담을 수 있는 것들의 무게와 최대가치가 주어졌을때 주어진 무게를 넘지 않으면서 최대의 가치를 담을 수 있도록 해결하는 문제를 말합니다. 🔎 DP로 풀어가면 쉽게 해결할 수 있는 문제로, DP문제의 대표적인 유형입니다. 아래의 간단한 대표 문제로 살펴보면 (문제) 최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다. 이 보석들의 가치는 각각 4,5,10,11,13이다. 이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야 할까요? 각 종류별 보석의 개수는 무한이 많다. 한 종류의 보석을 .. 2022. 12. 29. 이전 1 다음