[백준, 12865번] 평범한 배낭 (다이나믹 프로그래밍 : DP, 배낭 문제 : Knapsack, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 평범한 배낭" 문제는 knapsack 알고리즘 중 0/1 knapsack 알고리즘을 사용하여 풀 수 있는 대표적인 문제입니다.

 

배낭의 무게 제한이 존재하고, 물건은 무게와 가치를 가집니다. 이 때 배낭에 최대한 가치있는 물건만을 담을 수 있는 가치의 최댓값을 출력해야합니다.

 

0/1 knapsack 알고리즘에 대한 내용은 위 포스팅에서 확인 가능합니다.

---

4 7
6 13
4 8
3 6
5 12

 

예제 1번을 예로들어 설명하자면,

행은 각 물건의 정보를, 열은 가방에 담을 수 있는 무게를 나타내며, 각 칸(dp[i][w])은 i번째 물건까지 고려했을 때 무게 w에서 얻을 수 있는 최대 가치를 저장합니다.

 

배낭(Knapsack) 알고리즘의 핵심은 주어진 자원(무게와 가치)을 고려하여 배낭의 용량을 초과하지 않으면서최대 가치를 얻는 조합을 찾는 것입니다.

첫 번째 물건 (6,13) 

 

물건의 무게가 6이므로, 가방의 허용 무게가 6 미만일 때는 물건을 넣을 수 없습니다. 따라서 k < 6인 모든 칸은 이전 상태의 값(0)을 그대로 가져옵니다.

 

가방의 허용 무게가 6이 되었을 때, 처음으로 이 물건을 넣을 수 있게 됩니다. 이때의 계산 과정은:

1. 현재 물건을 넣고 남은 무게(6-6=0)에서의 이전 최적값(0)을 찾습니다.
2. 여기에 현재 물건의 가치(13)를 더해 새로운 값(13)을 구합니다.
3. 이 값과 이전 상태의 값(0)을 비교하여 더 큰 값(13)을 선택합니다.

무게 7의 경우도 같은 방식으로 계산하여 최대 가치 13을 얻을 수 있습니다.

 

즉, 각 단계에서 물건을 넣을 수 있는지 확인하고, 넣을 수 있다면 이전 상태의 최적값을 활용하여 새로운 최적값을 계산해나가는 것이 DP의 핵심입니다.

---

이 때 이전 값은 바로 윗칸(dp[i-1][w])으로, 현재 무게에서 현재 물건을 고려하기 전까지의 물건들로만 만들 수 있는 최적의 가치를 의미합니다.

 

(6,13) 물건을 k=6일 때 고려할 때, 바로 윗칸의 0은 현재 물건을 넣지 않았을 때의 값이고, 물건을 넣는 경우는 남은 무게(6-6=0)의 윗칸 값(0)에 현재 물건의 가치(13)를 더한 13이 됩니다. 이 두 값을 비교하여 더 큰 값인 13을 선택합니다.

이는 0/1 knapsack 알고리즘의 핵심인 '현재 물건을 선택하는 경우와 선택하지 않는 경우 중 최적값을 선택하는 과정'을 보여줍니다.

---

두 번째 물건 (4,8) 

 

두 번째 물건 (4,8)도 마찬가지로, 현재 물건을 선택할지 말지를 결정하며 최적값을 업데이트해 나갑니다.

 

예를 들어 k = 6일 때를 보면, 현재 물건의 무게가 4이므로 선택할 수 있습니다. 

1. 물건을 선택하는 경우: 남은 무게(6-4=2)의 윗칸 값(0)에 현재 물건의 가치(8)를 더한 8
2. 물건을 선택하지 않는 경우: 바로 윗칸의 값(13)

이 두 값을 비교하여 더 큰 값인 13을 선택합니다.

---

이런식으로 계속해서 업데이트 해나가면 다음과 같은 DP배열이 형성됩니다.

그러면 최종 최대 가치는 dp[N][K], 즉 DP 배열의 가장 마지막 행의 가장 마지막 열에 위치합니다.

---

전체 코드 

 

dp[i][w] = Math.max(
                            dp[i-1][ w - knapsack[i][0] ] + knapsack[i][1], dp[i-1][w]
                    );

 

배낭에 물건을 넣을 수 있을 때 Math.max() 메서드를 사용하여 바로 윗칸(dp[i-1][w])값과 현재 물건을 배낭에 넣었을 때의 가치(dp[i-1][w-knapsack[i][0]] + knapsack[i][1])를 비교하여 더 큰 값으로 업데이트합니다.