[백준_12865번] 평범한 배낭

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

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)가 주어진다. 입력으로 주어지는 모든 수는 정수이다.

 

[코드]

import java.util.Scanner;

public class BaekJoon_12865 {
	public static int dp[][],w[],v[];
	public static int n,k;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		k=sc.nextInt();
		
		/* 
		 * dp는 dp[i번째 아이템][무게]를 의미한다.
		 * 아이템의 개수는 n개 제한된 무게는 k이며,
		 * 1부터 인덱스를 시작하기 위해 아래와 같이 초기화를 한다.
		 */
		dp=new int[n+1][k+1];
		w=new int[n+1];
		v=new int[n+1];
		
		for(int i=1;i<=n;i++) {
			w[i]=sc.nextInt();
			v[i]=sc.nextInt();
		}
		
		/* 
		 * dp의 각 행은 n개의 아이템을 의미하고, 열은 k까지의 무게를 의미한다.
		 * 첫 번째 아이템부터 1~k 무게 이내로 담을 수 있는지 판단하고 담을수 있다면 가치를 저장한다.
		 * 이때 dp[i][j]는 이전 행의 누적 값을 갖는데 해당 아이텀을 담고도 무게가 남는다면
		 * 남는 무게만큼의 아이템을 더하여 이전 행의 누적 값과 비교하여 큰 값을 선택한다.
		 */
		
		for(int i=1;i<=n;i++) { // n개의 아이템을
			for(int j=1;j<=k;j++) { // 1~k 무게까지 담을 수 있는지 비교
				dp[i][j]=dp[i-1][j]; // 이전 행의 무게 값을 갖는다.
				if(j-w[i]>=0) // 아이템을 담고도 무게가 남는다면
					// 이전 아이템에서 구한 가치 or 남는 무게 가치 + 자신의 가치 중 큰 값 선택
					dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
			}
		}
		System.out.println(dp[n][k]);
	}
}

 

[고찰]

 2차원 배열 dp의 행은 각 아이템을 의미하고, 각 열은 1부터 주어진 k까지의 무게를 의미한다. 주어진 예시로 문제를 풀어보면 아래와 같다. 예시 -> n=4, k=7, 아이템(무게, 가치)=(6 13), (4, 8), (3, 6), (5, 12). 이를 가지고 dp를 표로 그려보면 아래와 같다.

아이템	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 아이템
2번 아이템
3번 아이템
4번 아이템

 

 이제 1번 아이템부터 각 열에 해당하는 무게일 경우 배낭에 넣을 수 있는지 확인한다. 무게가 6인 1번 아이템은 1~5 무게 까지는 담을 수 없고, 6 부터 담을수 있다. 때문에 무게 6과 7에는 아이템 1번의 가치를 저장한다.

아이템	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 아이템	0	0	0	0	0	13	13
2번 아이템
3번 아이템
4번 아이템

 

 2번 아이템은 무게가 4이기 때문에 무게 4부터 담을 수 있다. 이때 초기 값은 이전 아이템이 각 무게마다 담은 가치들이 그대로 내려오게 된다. 이때 해당 아이템을 담고도 무게가 남는 경우는(무게 5, 6, 7) 이전 행의 값 or 남는 무게의 가치 + 자신의 가치 중 큰 값을 선택하게 된다. 예를 들어 무게 6인 경우 이전 값 13 or 남는 무게(6-4=2)의 가치인 0 + 자신의 가치 8  중 13이 크기 때문에 13을 저장한다. 무게 7도 마찬가지 이다.

아이템	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 아이템	0	0	0	0	0	13	13
2번 아이템	0	0	0	8	8	13	13
3번 아이템
4번 아이템

 

 3번 아이템은 무게가 3이기 때문에 무게 3부터 담을 수 있다. 이후 무게 4, 5, 6은 이전 행의 값이 더 크기 때문에 이전 행의 값을 사용하고 무게 7이 중요하다. 무게 3을 담으면 무게 4가 남게 된다. 그러면 이전 행의 값 13과 남는 무게(7-3) 4의 가치 8(dp[3-1][7-3] => dp[i-1][j-w[i]])에 자신의 가치 6을 더한 14가 크기 때문에 14가 저장된다.

아이템	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 아이템	0	0	0	0	0	13	13
2번 아이템	0	0	0	8	8	13	13
3번 아이템	0	0	6	8	8	13	14
4번 아이템

 

 마지막 4번 아이템은 무게가 5이기 때문에 무게 5부터 담을 수 있다. 무게 4때는 이전 행의 값을 가져오고, 무게 5, 6 7일 때는 이전 행의 값 or 남는 무게의 가치 + 자신의 가치 중 큰 값을 선택하여 저장한다. 최종적으로 모든 값이 저장된 dp는 아래와 같고 마지막 값이 누적합의 최대가 된다.

아이템	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 아이템	0	0	0	0	0	13	13
2번 아이템	0	0	0	8	8	13	13
3번 아이템	0	0	6	8	8	13	14
4번 아이템	0	0	0	8	12	13	14

 

 이번 문제는 대표적인 동적 계획법 문제인 "냅색 문제" 였다. 처음 접해보는 유형이다 보니 어떻게 접근할지 몰라 여러 사람들의 풀이를 참고하였다. dp 표를 채우는 법을 이해하는데 조금 시간이 걸렸지만 이를 코드로 옮기는 과정은 간단했다. 대표적인 문제인 만큼 내것으로 만들수 있도록 여러번 반복해야겠다고 생각한다.