알고리즘 배낭문제

가장 흔한 문제인 배낭문제는 다양한 문제 풀이법이 있습니다. 먼저 가장 쉽게 재귀로 풀어보겠습니다. 재귀는 내가 이재품을 살때와 안살때를 재귀함수로 구현해주면됩니다. 일단 간단하게 배낭크기를 10으로 잡고 5개의 물건이 있다고 보면됩니다. 간단한 코드는 위와같다. 하지만 위의 코드는 계산했음에도 불구하고 계산할려는 특징이 있어 메모리로 계산을 했는지 안했는지 추가해야합니다. 이를 가지치기라고 하는데 다음에 설명하고 메모리DP를 풀겠습니다. dp로 답을 구하는법은 소개 더보기 알고리즘 배낭문제[…]