백준 12865번 평범한 배낭
평범한 배낭은 배낭의 최대 무게에 맞게 주어진 물건을 넣었을 때 얻을 수 있는 가치의 최대합을 구하는 문제다. 문제의 이름은 '평범한' 배낭이지만 실상은 전혀 평범하지 않은 문제다.. n번째 물건의 무게를 W(n), 가치를 V(n) 이라고 한다면 다음과 같이 나열할 수 있다. W(1), V(1) = 6, 13 W(2), V(2) = 4, 8 W(3), V(3) = 3, 6 W(4), V(4) = 5, 12 이를 활용해 가방에 담을 수 있는 최대 무게에 따른 1~4번 까지 물건과 그 때의 최대 가치를 표로 그려보면 몇 가지 규칙을 발견할 수 있다. (칸에 담기는 숫자의 의미는 최대 가치다.) ※ 참고로 세로줄은 n번 물건까지 탐색했다는 의미이다. 물건 (W, V) 0 kg 1 kg 2 kg 3 kg 4 k..
2023. 3. 17.
