[백준/자바] 12865번: 평범한 배낭

문제

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

풀이

• 여행에 필요하다고 생각하는 물건 N개
• 각 물건은 무게 W와 가치 V를 가짐
• 최대 K만큼의 무게만을 넣을 수 있는 배낭
• 배낭에 넣을 수 있는 물건들의 가치의 최댓값 출력

아주 기초적인 배낭 문제(Knapsack Problem)

배낭 문제에 대해 공부하고 싶으신 분은 밑에 링크로 이동하여 보시길 바랍니다.
굉장히 정리를 잘해놓으셨어요!
배낭 문제(KnapSack Problem) 그림으로 쉽게 이해하기

		info = new int[n+1][2];
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			info[i][0] = Integer.parseInt(st.nextToken()); // 무게
			info[i][1] = Integer.parseInt(st.nextToken()); // 가치
		}

무게와 가치를 한 번에 저장해 풀어봤습니다.

		dp = new int[k+1];
		for (int[] in : info) {
			int w = in[0]; // 무게
			int v = in[1]; // 가치
			
            // 최대 무게 ~ w까지 역순으로 탐색
            // 왜? i - w가 음수가 되면 안 되기 때문 !!
			for (int i = k; i >= w; i--) {
				dp[i] = Math.max(dp[i], dp[i-w] + v);
			}
		}

이 문제에서는 굳이 이럴 필요는 없지만, 공간복잡도를 고려해 1차원 dp 배열을 생성하여 풀었습니다.

dp[i] = Math.max(dp[i], dp[i-w] + v);

이 문제에서 가장 중요한 것은 바로 이 점화식입니다.

i번째 물건을 선택하느냐, 선택하지 않느냐를 나타낸 것입니다.
선택하지 않았다면 값을 업데이트하지 않고
선택했다면 선택한 무게만큼 공간을 줄여버리고 가치를 높이는 겁니다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, k;
	static int[] dp;
	static int[][] info;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		info = new int[n+1][2];
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			info[i][0] = Integer.parseInt(st.nextToken());
			info[i][1] = Integer.parseInt(st.nextToken());
		}
		
		dp = new int[k+1];
		for (int[] in : info) {
			int w = in[0];
			int v = in[1];
			
			for (int i = k; i >= w; i--) {
				dp[i] = Math.max(dp[i], dp[i-w] + v);
			}
		}
		
		System.out.println(dp[k]);
	}
}