[C++] 백준 12865 - 평범한 배낭

🔐 백준 12865 - 평범한 배낭

https://www.acmicpc.net/problem/12865

🔑 풀이

전형적인 0/1 배낭 문제로 DP를 통해 해결할 수 있다. 주어진 무게 제한을 넘지 않으면서

배낭에 넣을 수 있는 물건의 가치 합을 최대화해야 하기 때문에, DP 배열을 통한 최적 해를 찾는

방식으로 답을 도출할 수 있다.

배낭 문제는 크게 배낭에 넣을 물건을 쪼갤 수 있느냐 없느냐로 나눌 수 있다.
짐을 쪼갤 수 있는 경우를 Fractional knapsack problem이라 하고, 아닌 경우를
0-1 knapsack problem 이라 한다.

2차원 배열을 이용하여 dp[i][j]를 물건 i까지 고려했을 때, 배낭의 용량이 j일 때 얻을 수 있는

최대 가치를 의미한다고 정의하여 풀 수도 있지만, 1차원 배열로도 충분히 해결할 수 있다.

dp[i] = 무게 i까지의 최대 가치라고 두고, 각 물건의 무게와 가치를 입력받으며 하나씩 처리한다.

🧩 코드