[Java] 동적 프로그래밍(DP, Dynamic Programming) / 백준 12865번 / 배낭 문제

 

DP가 무엇인지 실마리를 잡고 싶다면

위 영상을 추천합니다.

💡 백준 12865번

🔖 # 문제 : 풀러가기 🔗

 

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

 

⌨️ # 입력

 

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

 

🖨️ # 출력

---

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

 

이 문제는 대표적인 배낭(knapsack) 문제입니다.

무게 제한이 주어진 배낭에 여러 물건을 넣어 총 가치를 최대로 만드는 문제입니다.

 

배낭 문제에서는
1. 짐을 쪼개어(한 짐의 전체가 아닌 일부만) 넣을 수 있는 유형이 있고 (Fractional 유형이라고 합니다.)

2. 짐을 쪼개어 넣을 수 없는 유형이 있습니다. (넣거나 말거나, 0-1 유형이라고 합니다.)

 

보통 첫 번째 유형에서는 그리디 알고리즘을 쓰고, 두 번째 유형에서는 DP를 사용합니다.

이번 문제 역시 짐을 쪼개 넣을 수 없는 문제로, DP를 사용해 풀 수 있습니다.

 

DP(동적 프로그래밍)로 풀기

이 DP란 무엇일까요?

큰 문제를 작은 문제로 쪼개서,
겹치는 부분 문제의 결과를 저장하고 재활용하는 방식

예를 들어 피포나치 수열 `f(n) = f(n-1) + f(n-2)`라고 할 때

n번째 항을 구할 때 n-2번째 항들은 이미 계산을 했을 겁니다. 매번 새롭게 계산할 필요는 없습니다.

이처럼 똑같은 값을 여러 번 계산하지 않기 위해 저장해두는 것이 DP입니다.

 

코딩테스트에서 기본적인 DP를 푸는 공식을 나름대로 세워봤습니다.

 

<💡 DP 문제 푸는 공식>

1. 큰 문제와 작은 문제 정의하기 2. 2차원 배열과 같은 DP 표 만들기 3. 점화식 세우기(작은 문제를 이용해 큰 문제를 풀 수 있도록) 4. 점화식에 따라 DP 표 채워가기 4. 표를 보고 답 찾기

 

백준 12865번에서

큰 문제는 문제 그 자체인, N개의 물건 중 일부를 골라서 총 무게 <= k인 배낭에 넣었을 때 가치의 최댓값입니다.

이 큰 문제를 여러 문제로 나누어 생각할 수 있습니다.

이때 작은 문제는 각 짐에 순서를 매겨두고, 첫번째부터 i번째까지 물건 중에 고려했을 때 무게 제한을 지키면서 얻을 수 있는 최대 가치가 됩니다.

(첫번째부터 i번째까지 물건을 다 넣는 게 아니라 그 중에서 가치가 가장 큰 조합으로 구한 가치의 값만 기억하면 됩니다.)

 

즉, 매번 "이 물건을 넣을까? 말까?"를 가치의 총합을 기준으로 결정하는 문제입니다.

작은 문제를 풀어서 구한 값들을 저장해가며 큰 문제를 풉니다.

---

앞에서 푼 값을 저장하는 곳이 바로 DP 표입니다.

보통 2차원 배열 형태로 많이 합니다.

 

우리가 구해야하는 건 가치의 최댓값이니까, 각 원소는 가치의 합이라고 합시다.

이때 조건이 1~i번째 물건까지 고려했을 때, 무게 제한 w를 지키면서니까

행을 물건, 열을 현재 넣을 수 있는 최대 무게라고 고려해봅시다.

 

물건은 최대 N개이니 1번 물건부터 N번 물건까지 있을 겁니다.

배열의 인덱스를 고려하여 0번 물건부터 N-1번 물건까지 있다고 생각합시다.

행(row)	의미
i(0~N-1)	물건 i번째까지 고려
w(0~k)	현재 배낭 무게 제한

 

즉, dp[i][w] = "앞에서부터 i번째 물건까지 조합을 고려했을 때 무게 w 이하로 넣을 때 최대 가치"가 됩니다.

---

그럼 이 DP 표를 채워나가기 위한 규칙, 점화식을 세워봅시다.

 

각 물건의 무게와 가치가 순서대로 각각 W, V 배열에 저장되어 있다고 합시다.

 

핵심적인 내용은, "i번째 물건을 넣을까, 말까?"입니다.

• i번째 물건이 최대 무게 제한보다 커서 넣을 수 없다면
  •  가치가 추가되지 않습니다 = 이전 i-1번째까지 얻은 최대치 그대로 사용합니다.
• 넣을 수 있다면, 넣었을 때와 안 넣었을 때 더 좋은 경우를 선택합니다.
  • 이 물건을 넣을 때, 가치가 최대가 된다면
    • 전체 무게에서 이 물건의 무게를 빼고 남은 무게에서 얻을 수 있는 최대치를 찾고, 그 값에 현재 물건의 가치를 더한다
  • 이 물건을 넣을 때, 가치가 최대가 아니라면
    • 이전 i-1번째까지 얻은 최대치 그대로 사용합니다.
  • 위 둘 중 더 큰 값으로 사용합니다.

if(W[i] > w) {	// i번째 물건을 배낭에 넣을 수 있는가? = 무게 제한을 지키는가
	// 못 넣는다면 이전 i-1번째 물건까지 고려한 최대치와 똑같이
	dp[i][w] = dp[i-1][w];	
} else {
	// 물건을 넣게 된다면 2가지 경우 중 더 큰 값으로
    // i번째 물건을 넣는 경우 -> 남은 무게(w-W[i]) 제한을 지키면서 얻을 수 있는 가장 큰 가치 + i번째 물건의 가치
    // i번째 물건을 안 넣는 경우 > i-1번째 물건까지 고려한 경우와 동일한 값으로
	dp[i][w] = max(dp[i-1][w], dp[i-1][w-W[i]] + V[i]);
}

 

이해가 안 된다면 예시를 보면서 이해해보세요 ㅎㅎ

---

위에서 세운 점화식으로 표를 채워나갑니다.

코딩테스트를 풀 때는 바로 코드로 나타내면 되지만, 우리가 세운 점화식이 맞는지 확인할 겸

그림으로 그려봅니다.

 

다음 예제를 사용해봅시다.

 

표를 다음과 같이 만들었습니다.

행에는 어떤 물건을 넣었는지 위해 i번째 물건을, 열에는 무게를 표시합니다.

최대 가능한 무게가 0일 때 얻을 수 있는 가치부터 목표인 7일 때 얻을 수 있는 가치까지 모두 계산합니다.

무게가 0이거나 1 또는 2일 때는 들어갈 수 있는 물건이 없어 0으로 미리 채워놨습니다.

 

그럼 최대 무게 w=3일 때는 어떻게 될까요?

2번째 물건이 무게가 3으로 배낭에 들어갈 수 있습니다. 

 

그렇다면 2번째 물건을 넣었을 때 최댓값을 구하면 됩니다.

무게가 3일 때 1번째 물건까지 고려한 최대치는 0이고,

남은 무게 0으로 2번째 물건까지 고려했을 때에 현재 2번째 물건의 값을 더한 값은 6이므로 더 큰 6이 채워집니다.

if(W[i] > w) {
	dp[i][w] = dp[i-1][w];	
} else {
	dp[i][w] = max(dp[i-1][w], dp[i-1][w-[W[i]] + V[i]);
}

---------------------------------------------------

i = 2, w = 3;
W[i] = 3, V[i] = 6;

if(W[2] > 3) {
	dp[2][3] = dp[1][3];	
} else {
	dp[2][3] = max(dp[1][3], dp[1][3-3] + 6);
}

3번째 물건을 넣을 때는

무게가 5인 물건을 넣을 수 없으니 2번째 물건까지 고려했을 때 얻을 수 있는 최댓값을 그대로 사용합니다.

 

앞에서 하던 것처럼 dp[1][4]까지 채웁니다.

 

2번째 물건도 1번째 물건처럼 배낭에 들어갈 수 있습니다.

이러면 어떤 값이 최대인지 비교해야 합니다.

이전 1번째 물건까지 고려했을 때 값 = 8 vs 현재 물건의 가치(6) + 남은 무게 1에서 1번째 물건까지 고려했을 때 최대치(dp[1][0]) = 6 으로 max = 8이 됩니다.

 

최종적으로 채워진 표는 다음과 같습니다.

답은 무게 7에서 3번째 물건까지 모두 고려한 가치의 최대치 14가 됩니다.

---

코드로 작성해봤습니다.

import java.util.*;
import java.lang.Math;

public class Main {
  public static void main(String[] args) {
    // 초기 입력
    Scanner sc = new Scanner(System.in);
    int itemNumbers = sc.nextInt();
    int maxWeight = sc.nextInt();
    int[] itemWeights = new int[itemNumbers];
    int[] itemValues = new int[itemNumbers];

    for(int i=0; i<itemNumbers; i++) {
      itemWeights[i] = sc.nextInt();
      itemValues[i] = sc.nextInt();
    }

    // dp 표 채우기
    int[][] dp = new int[itemNumbers][maxWeight+1];
    for(int w=0; w<maxWeight+1; w++) {
      for(int i=0; i<itemNumbers; i++) {
        if(itemWeights[i] <= w) {
          int unincludedValue = (i>=1)? dp[i-1][w]:0;;
          int includedValue = itemValues[i] + ((i>=1)? dp[i-1][w-itemWeights[i]]:0);
          dp[i][w] = Math.max(unincludedValue, includedValue);

        } else {
          dp[i][w] = (i>=1)? dp[i-1][w]:0;
        }
      }
    }
    System.out.println(dp[itemNumbers-1][maxWeight]);
  }
}