백준 12865번 - 평범한 배낭

solved.ac 백준 골드문제 포스팅

문제

Knapsack 알고리즘

문제를 보면 흔히 일어날 수 있는, 즉 많이 사용될만한 문제이다.
이런 일이 아주 많아서인지 이름도 있었다. Knapsack
이러한 알고리즘에서 가장 중요한 것은 2차원 배열로 메모이제이션 하는 것이다.

위와 같은 입력을 메모이제이션하여 표로 그려보면 다음과 같다.

우선 이전 입력을 넣고, 현재의 value가 더 크면 현재의 value를 넣는다.
만약 이전 입력의 무게와 현재의 무게가 한계 무게보다 작거나 같으면, 그 합을 넣는다.
이를 점화식으로 표현하면 다음과 같다.
(출처 : https://gsmesie692.tistory.com/113)

접근법

사실 수식을 알고 있으면 좋지만, 문제를 풀 때에는 이게 무슨 알고리즘인지, 무슨 수식이 정형화 되있는지 잘 모르고 풀었다.
2차원 배열로 메모이제이션한다는 이야기를 듣고 힌트를 얻어 한번 해보았고, 저 표를 그리는 로직을 코드로 구현할 수 있다면 된다.

코드 - JAVA

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


class Main {
    static int weight = 0;
    static int N = 0;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer str = new StringTokenizer(br.readLine());
        N = Integer.parseInt(str.nextToken());
        weight = Integer.parseInt(str.nextToken());
        int dp[][] = new int[N+1][weight+1];
        //메모이제이션용 2차원 배열
        for(int i=1; i<=N; i++) {
            str = new StringTokenizer(br.readLine());
            int inputWeight = Integer.parseInt(str.nextToken());
            int value= Integer.parseInt(str.nextToken());
            for(int j=1; j<=weight; j++){
                dp[i][j] = dp[i-1][j];
                //먼저 기존 값을 넣는다.
                if(j-inputWeight>=0){
                //j값은 배열을 채워나가며 무게
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-inputWeight]+value);
                    // 기존 값과 value를 더한 새로운 값 중 큰 것을 dp배열에 넣기
                }
            }
        }

        System.out.print(dp[N][weight]);
    }
}