평범한배낭

[Baekjoon] 12865 평범한 배낭 문제

https://www.acmicpc.net/problem/12865 배낭 문제는 냅색 알고리즘의 대표 문제라고 할 수 있다. 냅색 알고리즘은 다이나믹 프로그래밍에 속하는 알고리즘이다. 문제의 입력 예제를 통해 냅색 알고리즘에 대해 알아보자. 1. 먼저 넣을 수 있는 무게 크기만큼 1차원 배열을 하나 준비하자. (dy라고 하겠다) 2. 첫 번째 경우(4kg, 8원) 4kg의 가방에 8원의 가치를 가진 물건을 하나 넣을 수 있다. 5 - 7까지 모두 동일하다. 3. 두 번째 경우(5kg, 6원) 5kg의 가방에 6원의 가치를 가진 물건을 넣을 수는 있지만 이전 값인 8이 더 크므로 4kg, 8원짜리 물건을 넣는다. 4. 세 번째 경우(3kg, 2원) -> 3kg의 가방에 2원짜리 물건을 넣을 수 있다. ->..