[Algorithm] 백준_12865 평범한 배낭 JAVA

문제

준서의 배낭에 K 무게 만큼의 물건들을 들고갈 수 있는데 각 물건은 무게와 가치를 가진다. 이때 가져갈 수 있는 물건들의 최대 가치값을 출력하면 되는 문제이다.

풀이

어떻게 풀어야하는지 감이 안와서 검색해서 풀었다.

• 가로는 물건, 세로는 무게인 2차원 배열이 필요하다.
• 2차원 배열에는 물건을 하나씩 추가하면서 무게가 j일 때 넣을 수 있는 물건들의 가치 합을 넣어준다.
• dp[i][j]에는 기본적으로 이전 아이템(이전 행)으로 해당 무게를 채울 수 있는 경우를 넣어준다.

dp[i][j] = dp[i-1][j];

• 무게(j)보다 넣어야하는 물건(i)의 무게가 작거나 같은 경우 (다른 물건을 더 넣을 수 있는 경우)

 dp[i][j] = Math.max(dp[i-1][j-temp_w] + temp_v, dp[i][j]);

나머지 무게(j-물건 무게)만큼 넣을 수 있는 값을 더한 후, 현재 있는 값과 최대값 비교 후 넣는다.

1	2	3	4	5	6	7
0	0	0	0	0	13	13
0	0	0	8	8	13	13
0	0	6	8	8	13	14
0	0	6	8	12	13	14

소스 코드

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

public class BOJ_12865 {
    static int N; //물건 개수
    static int K; //무게
    static int[][] dp;
    static ArrayList<Product> products = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        dp = new int[N+1][K+1];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            int w = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            products.add(new Product(w, v));
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                int temp_v = products.get(i-1).v;
                int temp_w = products.get(i-1).w;

                dp[i][j] = dp[i-1][j];

                if (j >= temp_w) {
                    dp[i][j] = Math.max(dp[i-1][j-temp_w] + temp_v, dp[i][j]);
                }
            }
        }


        System.out.println(dp[N][K]);
    }

    static class Product {
        int w;
        int v;

        public Product(int w, int v) {
            this.w = w;
            this.v = v;
        }
    }
}

후기

흠.. DP문제 풀 때 점화식 조건을 꼼꼼히 생각하면서 풀어야할 것 같다.