[JAVA] 백준 12865 평범한 배낭(with knapsack)

 

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

 

문제분석

knapsack(냅색) 알고리즘에 대해 처음 배우게 된 문제였다.

DP 방식으로 냅색 알고리즘을 구현하면 된다.

 

knapsack알고리즘이란?

이 문제를 기준으로 설명하면 다음과 같다.

n번째 물건을 가방에 넣을 때를 보면, 3가지 상황이 존재한다.

1. n번째 물건이 가방 크기보다 큰 경우

2. n번째 물건이 가방 크기보다 작은 경우일 때

2-1. n-1번째 물건을 넣었을 때(n번째 물건을 넣지 않았을 때)가, 어떻게든 n번째 물건을 넣었을때 보다 가치가 큰 경우

2-2. n-1번째 물건을 넣었을 때보다, 어떻게든 n번째 물건을 넣었을때가 가치가 큰 경우

따라서, 2차원 배열 int[N+1][K+1]를 활용한다. 배열의 [n][k]는 가방의 최대 무게가 k일 때, n번째 물건을 확인하여 저 3가지 상황을 거쳐 해당 가방의 최대 가치를 저장한다.

 

냅색 알고리즘은 bottom-up 방식의 DP로 구현하면 손쉽게 구현이 가능하다. 중요한점은 어떻게든 n번째 물건을 넣었을 때 를 계산할때, column에서 현재 추가할 stuff무게만큼 빼기에 col->row 순으로 2차원 배열을 채워나가야 한다는 것이다.

 

 

코드

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

public class Main{
    public static void main(String[]args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = br.readLine().split(" ");

        int N = Integer.parseInt(temp[0]);
        int K = Integer.parseInt(temp[1]);
        int[][] knapsack = new int[N+1][K+1]; // 인덱스가 N까지, 무게가 K까지여야 함.'가치' 저장함.
        int[][] stuff = new int[K][2];//[k][0]은 무게, [1]은 가치
        
        for(int n = 0; n < N; n++){
            temp = br.readLine().split(" ");
            stuff[n][0] = Integer.parseInt(temp[0]);
            stuff[n][1] = Integer.parseInt(temp[1]);
        }

        for(int i = 0; i < N+1; i++){
            Arrays.fill(knapsack[i],0);
        }
        
        for(int n = 1; n < N+1; n++){
            for(int k = 1; k < K+1; k++){
                if(k<stuff[n-1][0]){ // 가방의 최대 무게 k보다, i번째 물건의 무게가 더 무거운 경우 - 물건 더 추가 불가
                    knapsack[n][k] = knapsack[n-1][k];
                }else{ // 추가 가능할 수 있는 경우 - knapsack[i-1][k]과 knapsack[i-1][k-물건 무게]+ 물건 가치 중 최대값
                    knapsack[n][k] = Math.max(knapsack[n-1][k],knapsack[n-1][k-stuff[n-1][0]]+stuff[n-1][1]);
                }
            }
        }
        System.out.println(knapsack[N][K]);
    }
}