[백준] 12865, 평범한 배낭(java)

1. 문제 : 12865

2. 문제풀이

Knapsack 활용하면 바로 풀리는 문제!
다이나믹 프로그래밍 사용하면 된다.

• Knapsack
• n개의 물건과 각 물건 i의 무게 w와 가치 v가 주어지고, 배냥의 용량은 w일 때, 배낭에 담을 수 있는 물건의 최대 가치를 찾는 문제이다. 단, 배낭에 담은 물건의 무게의 합이 W를 초과하지 말아야 하고, 각 물건은 1개씩만 있다.
• 이차원 배열에 각 무게마다 최선의 값을 저장한다.
• 간단하게 아래와 같은 점화식으로 표현할 수 있다.

for i in 1->n
	for w in 1->W
    	if(wi > w) k[i,w] <- k[i-1, w]
        else k[i,w] <- max(k[i-1,w], vi+k[i-1, w-wi])

3. 소스코드

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

//Knapsack Problem
public class Main_12865 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken()); // 물건 가지수
		int K = Integer.parseInt(st.nextToken()); // 최대 무게
		
		int[][] arr = new int[N+1][2];
		int[][] dp = new int[N+1][K+1];
		
		// 입력 받기
		for (int i = 1; i <= N; i++) { // arr[i][0] : 무게, arr[i][1] : 가치
			st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
	
		for (int k = 1; k < K+1; k++) {
			for (int i = 1; i < N+1; i++) {
				 dp[i][k] = dp[i - 1][k];
				if(k - arr[i][0] >=0) { // i번째 물건의 무게가 k보다 작을 때
					dp[i][k] = Math.max(dp[i][k], arr[i][1] + dp[i - 1][k - arr[i][0]]);
				}
			}
		}
		System.out.println(dp[N][K]);
	}
}