BOJ G5 12865 평범한 배낭 JAVA

문제 읽기

해당 문제는 가장 기본적인 0-1 Knapsack 문제이다.

DP에 대한 이해를 위해 직접 표를 그려보자

예제 1

4 7
0: 6 13 (무게, 가치)
1: 4 8
2: 3 6
3: 5 12

 

물건개수/남은부피	1	2	3	4	5	6	7
0	0	0	0	0	0	13	13
1	0	0	0	8	8	13	13
2	0	0	6	8	8	13	14
3	0	0	6	8	12	13	14

 

둘 다 인덱스를 0부터 시작하면

남은 부피의 경우에는 비교를 하게 되기 때문에 인덱스 + 1을 한 상태가 실제 남은 부피가 되고, 이렇게 비교해줘야 한다.

 

따라서 그냥 k의 경우에는 1부터 k까지 설정하는 것이 좋다.

또한 N도 이전 컬럼을 보면서 비교하기 다음 컬럼을 채워나가기 떄문에 1부터 시작하는 것이 좋다.

 

즉, 점화식을 보고 DP 배열은 여유 공간을 주고 시작하자.

 

코드

package ps.ㄱSolving;

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

public class BOJ_G5_12865_평범한배낭 {

    /*
    N개의 물건, 물건마다 무게 W, 가치 V
    배낭의 최대 용량 K

    - 자료구조
    입력 자료구조
    int[][]

    DP 자료구조
    int dp[i][j] : 이차원 int 배열.
    i : 1~i번째 물건을 넣었을 때
    j : 배낭의 무게가 j 이하일 때
    가치의 최댓값을 dp[i][j]에 저장
     */
    static int N, K;

    public static void main(String[] args) throws IOException {

        //input
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(in.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        int[][] items = new int[N][2]; //무게, 가치
        for (int i = 0; i < N; i++){
            st = new StringTokenizer(in.readLine());
            for (int j = 0; j < 2; j++){
                items[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //logic : DP
        int[][] dp = new int[N+1][K+1]; //가방 용량이 j일때 1~i번째 물건까지 넣었을 때의 최대 가치
        //물건을 하나씩 늘려가면서
        for (int i = 1; i < N+1; i++){
            //그리고 부피를 하나씩 늘려가면서 값을 업데이트
            for (int j = 1; j < K+1; j++){ //남은 가방의 부피!!
                /*
                dp[i][j]
                1. i번쨰 물건을 넣을 수 없다 가치 값은 dp[i][j-1]과 같다.
                2. i번째 물건을 넣을 수 있다.
                2.1 현재 물건의 가치를 더해준다

                둘 중 큰 값을 선택한다.

                즉, dp[i][j]에는 dp[i][j-1]의 값을 먼저 넣어두고,
                물건을 넣을 수 있다면 최댓값을 비교함으로써 해결할 수 있다.
                 */
                dp[i][j] = dp[i-1][j];
                if (items[i-1][0] <= j){ //가방에 물건을 넣을 수 있다면
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-items[i-1][0]] + items[i-1][1]);
                }
            }
        }

//        for (int i = 0; i < N; i++){
//            System.out.println(Arrays.toString(dp[i]));
//        }
        System.out.println(dp[N][K]);
    }
}