Baekjoon | Q.12865 - 평범한 배낭

12865번: 평범한 배낭

 배낭의 무게와 물건들의 가치와 무게가 함께 주어진다. 주어진 물건들을 이용하여 배낭의 값어치를 최대로 채우는 문제이다.

import java.util.Scanner;

public class Main {
  static int[][] items;
  static int[][] bag;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();

    items = new int[n][2];
    bag = new int[n][k+1];

    for (int i = 0; i < n; i++) {
      items[i][0] = sc.nextInt(); // 물건의 무게
      items[i][1] = sc.nextInt(); // 물건의 가치
    }
    
    sc.close();

    for (int i = 0; i < n; i++) {
      int w = items[i][0];  // 물건의 무게
      int v = items[i][1];  // 물건의 가치
      for (int j = 1; j < k + 1; j++) {
        if(i == 0) {  // 첫 물건은
          if(w <= j) {  // 가방에 들어가는 무게라면
            bag[i][j] = v;  // 가방을 채운다.
          }
        }else {
          bag[i][j] = bag[i-1][j];
          if(w <= j) {  // 무게가 가방 크기보다 작거나 같으면 가방에 들어갈 수 잇음
            int extra = j - w;  // 여유 공간
            int vTotal = v + bag[i-1][extra]; // 지금 물건의 가치 + 여유공간의 최대 가치
            if(bag[i-1][j] < vTotal) {  // 이전의 최대 가치보다 크다면
              bag[i][j] = vTotal; // 갱신
            }
          }
        }
      }
    }

    System.out.println(bag[n-1][k]);
  }
}

 가방 무게에 맞는 물건들의 모든 조합을 찾기 보다는 동적 프로그래밍을 이용하여 문제를 풀었다. 

 

 bag[n][k+1] 배열은 0~n번째 아이템까지의 물건 조합 중 무게가 k인 배낭에서 가지는 현재 최대 가치를 뜻한다.

 

 입력 예제를 살펴보자.

	무게(w)	가치(v)
item[0]	6	13
item[1]	4	8
item[2]	3	6
item[3]	5	12

 이 물건들을 가지고 무게가 7인 배낭을 채워보자.

	1	2	3	4	5	6	7
item[0]	0	0	0	0	0	13	13
item[1]
item[2]
item[3]

 0번째 물건만 배낭에 채우면 무게가 1-5인 배낭에는 들어가지 못하므로 최대 가치가 0, 무게가 6인 배낭부터 들어갈 수 있으므로 최대가치를 채워 넣는다.

	1	2	3	4	5	6	7
item[0]	0	0	0	0	0	13	13
item[1]	0	0	0	8 > 0 → 8	8+0 > 0 → 8	8+0<13 → 13	8+0<13 → 13
item[2]
item[3]

 1번째 물건을 이어서 채워보자. 무게가 4이므로 4인 배낭부터 들어갈 수 있다. 배낭에 집어 넣기 전, 이전에 기록한 최대 가치보다 큰지 작은지 비교하여 집어 넣을지 말지를 결정하도록 하자. 더 나아가 무게가 5 이상부터는 배낭의 여유공간이 생기게 된다. 이 여유 공간에 집어 넣을 수 있는 최대 가치를 탐색해서 합해주도록 하자. 

	1	2	3	4	5	6	7
item[0]	0	0	0	0	0	13	13
item[1]	0	0	0	8 > 0 →  8	8+0 > 0 →  8	8+0<13 → 13	8+0<13 → 13
item[2]	0	0	6	6+0 < 8 →  8	6+0 < 8 →  8	6+0<13 → 13	6+8>13 → 14
item[3]	0	0	6	8	12 > 8 →  12	12+0<13 →  13	12+0<14 → 14

 

 2번째, 3번째 물건도 마찬가지로 채우면 마지막 최종 최대 가치는 14가 나오게 된다.