BOJ 12865 - 평범한 배낭

12865번: 평범한 배낭

 

N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가진다.

최대 K만큼의 무게만 넣을 수 있는 배낭이 있을 때 가지고 갈 수 있는 물건들의 가치의 최댓값을 찾아라

1≤N≤100, 1≤K≤100,000, 1≤W≤100,000, 0≤V≤1,000

 

단위 무게당 가장 가치있는 물건을 넣어볼까 생각할 수 있다. 하지만 그러면 안 된다. 물건을 쪼갤 수 없을뿐더러 해당 경우가 최선의 경우인지 보장이 안된다.

완전탐색의 경우에는 해당 물건을 넣냐 안넣냐의 경우가 존재해 O(2^100)으로 불가능하다

결국 부분 문제의 해를 이용하는 DP를 써야한다.

dp 배열의 의미부터 정해보자. 물건을 넣냐 안 넣냐 와 무게 이 두 가지가 필요하다.

즉 dp[i][w] = i번 째 물건까지 고려했을 때, 무게 w를 사용해서 얻을 수 있는 최대 가치가 된다.

i 번 째 물건을 넣을 수 있는 경우가 넣을 수 없는 경우가 존재한다.

i번 째 물건을 넣을 수 있는데 넣는 경우와 안 넣는 경우도 존재한다.

i 번 째 물건을 넣을 수 있는 경우는 다음과 같다.

dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])가 된다.

i 번 째 물건을 넣을 수 없는 경우는 다음과 같다.

dp[i][w] = dp[i-1][w]

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

public class Main {

    static class Item {
        int weight;
        int value;

        Item(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }

    static FastReader scan = new FastReader();
    static int N;
    static int K;
    static Item[] items;

    static void input() {
        N = scan.nextInt();
        K = scan.nextInt();
        items = new Item[N + 1];
        for (int i = 1; i <= N; i++) {
            Item item = new Item(scan.nextInt(), scan.nextInt());
            items[i] = item;
        }
    }

    static void solve() {
        int[][] dp = new int[N + 1][K + 1];
        for (int i = 1; i <= N; i++) {
            for (int w = 1; w <= K; w++) {
                if (items[i].weight <= w) {
                    // 해당 아이템을 넣을 수 있는 경우
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - items[i].weight] + items[i].value);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        System.out.println(dp[N][K]);
    }

    public static void main(String[] args) {
        input();
        solve();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}