백준 12865 - 평범한 배낭 JAVA

문제, 입출력, 테스트케이스

해당 문제는 DP의 대표적인 냅색(Knapsack-짐싸기)문제라고 한다. 하지만 본인은 1주일 동안 손을 대지 못하고 있었다.

왜냐하면 무게 W에 대해 중복된 가치를 가질 수 있는가에 대한 의문이 들었기 때문이다. 하지만 그건 기우였다. 중복된 가치가 되든 말든 상관이 없었다..!

 

흔한 뉴비를 구제해주시는 굇수분.jpg

단계별로 문제 풀기

드디어 동적 계획법 1까지 단계별로 풀기를 싹 밀었다! 하지만 5개월~6개월 전부터 시작해서 앞부분에 힘겹게 풀었던 것을 또 다시 풀라고 하면 풀 수 있을지는 의문이다. 

내 머릿속의 지우개ㅜㅜ 이상한 소리 하지 않고 바로 문제 풀이/접근과정과 소스코드 공유하겠슴다.

 

<문제 접근/풀이과정>
1. 1 <= 물품의 수 N <= 100 / 1 <= 준서가 버틸 수 있는 무게 K <= 100,000
2. 1 <= 물건 무게 W < 100,000 / 0 <= 물건의 가치 <= 1,000         => 최대가치의 합 100,000 -> int배열 가능
3. 점화식
- dp(n, w) = max(n번째 아이템을 포함하면서 최대인 경우 or n번째 아이템을 포함하지 않으면서 최대인 경우)
               = max(n번쨰의 k + dp(n-1,w-n번째w) or dp(n-1, w) (w > n번째 w)  

여느 DP문제처럼 점화식을 보고나면 매우 쉬운 문제... 

 

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj_12865 {
	public static void main(String[] args) throws IOException {
		// 1 <= 물품의 수 N <= 100 / 1 <= 준서가 버틸 수 있는 무게 K <= 100,000
		// 1 <= 물건 무게 W < 100,000 / 0 <= 물건의 가치 <= 1,000
		// 물건의 무게가 겹칠 수도 있음
		// 최대 100,000 -> int배열 가능
		// 점화식
		// 1. K보다 W가 작거나 같다.
		// 점화식
		// dp(n, w) = max(n번째 아이템을 포함하면서 최대인 경우 or n번째 아이템을 포함하지 않으면서 최대인 경우)
		// 		 = max(n번쨰의 k + dp(n-1,w-n번째w) or dp(n-1, w) (w > n번째 w)  

		
		int N, K, arr[][], dp[][];
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz;
		stz = new StringTokenizer(br.readLine());
		N = Integer.parseInt(stz.nextToken());
		K = Integer.parseInt(stz.nextToken());
		arr = new int[N+1][2];
		dp = new int[N+1][K+1];
		for (int i = 1; i <= N; i++) {
			stz = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(stz.nextToken());
			arr[i][1] = Integer.parseInt(stz.nextToken());
		}
		
		
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= K; j++) {
				if(j < arr[i][0]) { // 배낭 보다 무게가 큰 물품인 경우
					dp[i][j] = dp[i-1][j];
				}else {  // 고려할 배낭보다 무게가 작은 물품인 경우 
					dp[i][j] = Math.max(arr[i][1] + dp[i-1][j-arr[i][0]], dp[i-1][j] );
				}
			}
		}
		
		System.out.println(dp[N][K]);
	}
}