[알고리즘] 백준 12865 자바 JAVA 동적프로그래밍 냅색

 

 

 

처음에 풀 때는 1차원 배열에 인덱스를 무게, 값을 가치로 두고 풀었는데 원하는 방향으로 값이 나오지 않았다. 왜 안나오나 했더니 이전값과 비교하는 방식이 틀려먹어서였다.

 

public class BaekJoon_16_12865_2 {

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(reader.readLine());
		int N = Integer.parseInt(st.nextToken()); // 1 ~ 100
		int K = Integer.parseInt(st.nextToken()); // 1 ~ 100,000

		int[][] dp = new int[N + 1][K + 1]; // 0:W(무게), 1:V(가치)
		int[] W = new int[N + 1];
		int[] V = new int[N + 1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(reader.readLine());
			W[i] = Integer.parseInt(st.nextToken());
			V[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= K; j++) {
				dp[i][j] = dp[i - 1][j];
				if (j - W[i] >= 0)
					dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
			}
		}

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= K; j++) {
				System.out.print(dp[i][j] + "\t");
			}
			System.out.println();
		}

		writer.write(dp[N][K] + "");

		writer.flush();
		reader.close();
		writer.close();
	}

}

대략 코드는 이렇다. 

 

	WEIGHT 1	WEIGHT 2	WEIGHT 3	WEIGHT 4	WEIGHT 5	WEIGHT 6	WEIGHT 7
ITEM 1	0	0	0	0	0	13	13
ITEM 2	0	0	0	8	8	13	13
ITEM 3	0	0	6	8	8	13	14
ITEM 4	0	0	6	8	12	13	14

 

먼저 아이템 1일때를 보자. 사실 정말 별거 없다.. 다만 항상 알고리즘 문제는 컴퓨터가 어떻게 푸는게 좋을 지를 고민하는게 중요한 것 같다. 먼저 무게가 1일 때부터 저장하는 것이다. 일단 문제의 지문에서 아이템 1의 무게가 6이라서 1에는 들어갈 수가 없다! 2 .. 3.. 4.. 5.. 마찬가지로 6의 무게는 들어갈 수가 없기 때문에 무게는 쭉 0이다. (사실 인덱스가 1부터 시작이라 0인덱스의 값을 불러오는 건데 자바는 기본 초기화가 0이다.) 

 

아이템 2를 보자. 무게가 4이기 때문에 무게가 4일때부터 값이 들어가는데, 주의해야하는 것은 이전 아이템의 가치를 가져와서 비교해서 큰 가치를 값에 넣는 것이다. 

 

아이템 3을 보자 무게가 3인데 무게가 4인 부분에서 6이아닌 8일 저장되고 있다. 이전의 아이템의 가치와 비교했을 때 큰 값을 저장하는 것이다. 그러다가 무게가 7일때를 보니 급 14가 되는데, 이는 7에서 4만큼을 차지하는데 남은 3의 무게를 이전 아이템을 가져와서 더했기 때문에 가능한 일이다.

 

이렇게 쭉 디버깅 하면 14라는 결과가 나온다.