[BOJ 12865] 평범한 배낭

문제

• BOJ 12865
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

현재 물건(i)에서 현재 무게(j)까지 올 때 까지의 최대 가치를 dp[i][j]를 저장한다.

1. i번째 물건을 넣을 때 j무게까지 넣는 최대 가치가 이전에 저장되어 있으므로 처음엔 이전 가치를 무조건 넣는다. → dp[i][j] = dp[i - 1][j]

2. 만약, j-현재무게를 했을 때 남는 무게가 있으면 더 큰 가치를 구할수도 있으므로 현재 무게를 넣었을 때와 j-현재무게일때의 최대 가치를 더해서 1번값과 비교한다.

   → dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])

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

//평범한 배낭
public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, K; // 물건 개수, 버틸 수 있는 무게
	static int[] w;
	static int[] v;
	static int[][] dp; // 물건번호, 현재 무게까지 온 최대 가치

	public static void main(String[] args) throws NumberFormatException, IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		w = new int[N + 1];
		v = new int[N + 1];
		dp = new int[N + 1][K + 1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			w[i] = Integer.parseInt(st.nextToken());
			v[i] = Integer.parseInt(st.nextToken());
		} // End input

		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) { // 남는 무게가 있으면 이전 가치 vs 남은무게가치 + 현재가치 비교
					dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); 
				}
			}
		}
		System.out.println(dp[N][K]);
	}
}