Archive: 2020/6

0

기초 DP알고리즘 문제

배낭 알고리즘(a.k.a Knapsack problem)배낭 알고리즘은 쪼갤 수 없는 물건이 제한된 가방에 최대한의 가치로 담는 문제이다. Fractional Knapsack 문제는 탐욕 알고리즘으로 풀 수 있었지만, 조건에서 쪼갤 수 있어서 가능했다. 앞서 쪼갤 수 없는 물건을 최대한의 가치를 가지며 담기 위해서는 DP를 통해서 해결하게 된다. 알고리즘