knapsack

[알고리즘] 백준 12865 - 평범한 배낭

문제본문 입력 [물건의 개수] [최대 무게] 4 7 [물건 무게] [물건 가치] 6 13 4 8 3 6 5 12 ________________ 출력 [최대 가치] 14 동적프로그래밍의 대표 문제 불리는 Knapsack 알고리즘은 dp를 사용하여 무게와 가치 두 가지 요소로 가질 수 있는 최대 가치를 구하는 문제 유형이다. 문제 해설 동적프로그래밍은 dp를 어느 부분으로 잡는 지가 관건 인듯하다. Knapsack은 이중 배열로 dp를 설정한다. dp[i][j]라고 가정하면, i번째까지 물건을 집어 넣는 다고 했을 때, 남아있는 무게가 j라면 얻을 수 있는 최대가치를 뜻한다. 해당 알고리즘은 테이블로 과정을 묘사하면 이해가 더 쉽다. 무게 1 2 3 4 5 6 7 1번째 물건 0 0 0 0 0 13 13 2..