백준 12865 - 평범한 배낭(자바 - 동적 프로그래밍)

 

DP 에 대해 문제 풀이 역량이 스스로 너무 부족함을 절절히 느낀 문제

사용하는 방법이 비교적 명확한 다른 알고리즘들에 비해, 점화식을 세우는 방식이 워낙 각양각색 인지라 아직도 전형적인 동적 프로그래밍 풀이 문제를 제외하면(피보나치 수열과 비슷한 문제들) 다른 문제를 거의 풀지 못하는 내 자신의 부족한 역량을 뼈 속 깊이 느낄수 있었던 문제였다.

 

처음 이 문제를 마주했을 땐, 그리디 알고리즘을 공부할 때 배웠던 문제와 흡사했기 때문에 물건을 가중치 대비 무게가 낮은 순으로 정렬한 다음, 입력받은 최대 무게 k 만큼 가방이 찰 때까지 물건을 채워 넣다가 무게가 꽉 차면 지금까지 가방해 들어간 물건들의 가중치 합을 출력, 만약 가방에 담을 수 있는 무게 보다 이번에 들어갈 차례인 물건의 무게가 무겁다면 물건을 분할하여 배낭에 넣는 방식으로 코드를 작성했다.(전형적인 그리디 알고리즘 풀이법)

 

하지만 위와 같은 해결법은 틀렸습니다 라는 결과를 받았고, 그 이후 아무리 생각해도 이걸 어떻게 DP 를 활용하여 문제를 풀 수 있을지 생각나지 않았다.

결국 DP 문제를 풀기위한 점화식을 도저히 어떻게 세워야 할지 감이 잡히지 않아 결국 패스트 캠퍼스의 해설 강의를 참고하였다.

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

12865번: 평범한 배낭

 

핵심 아이디어

- 모든 무게에 대하여 최대 가치를 저장한다.

- D[i][j] = 배낭에 넣은 물품의 무게 합이 j 일 때 얻을 수 있는 최대 가치

- 각 물품의 번호 i 에 따라서 최대 가치 테이블 D[i][j] 를 갱신하여 문제를 해결할 수 있다.

- Main.java

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

public class Main {
	// 동적 프로그래밍을 이용하여 시간복잡도 O(NK) 로 문제를 해결 할 수 있다.
	/*
	 * 모든 무게에 대하여 최대 가치를 저장하기
	 * D[i][j] = 배낭에 넣은 물품의 무게 합이 j 일 때 얻을 수 있는 최대 가치
	 * 각 물품의 번호 i 에 따라서 최대 가치 테이블 D[i][j] 를 갱신하여 문제를 해결할 수 있다.
	 */
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int count = Integer.parseInt(st.nextToken());
		int maximum = Integer.parseInt(st.nextToken());
		int[][] objectArray = new int[count+1][maximum+1];
		
		for(int i = 1; i < count+1; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int weight = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			
			for(int j = 1; j < maximum+1; j++) {
				if(j < weight) {
					// 물건의 무게값이 현재 인덱스보다 큰 경우 이전 행의 데이터를 그대로 가져온다.
					objectArray[i][j] = objectArray[i-1][j];
				}
				else {
					// 그렇지 않을 경우 이전 행의 데이터와, 입력으로 들어온 물건의 가치 + 이전 행에서 (열 인덱스 - 무게) 인 열을 비교하여
					// 둘 중에 더 큰 쪽을 저장해둔다.
					objectArray[i][j] = Math.max(objectArray[i-1][j], objectArray[i-1][j-weight] + value);
				}
			}
		}
		
		// 2차원 배열의 가장 마지막 인덱스에 저장되어 있을 최대값을 출력한다.
		bw.write(objectArray[count][maximum] + "\n");
		bw.flush();
		bw.close();	
	}
}