[백준]12865. 평범한 배낭 - Java

📄 링크

평범한 배낭

---

💡 문제 분석

최대 K 무게를 담을 수 있는 배낭에 물품들을 담을 때, 가치를 가장 크게 할 수 있는 방법을 구하는 문제입니다.
일단 물품 수 100개 중에 몇 개인지 모를 물품을 골라 무게를 비교하는 완전탐색은 당연히 시간 초과가 날 것 같아서 메모이제이션를 사용하기로 했습니다

1. 일단 물품들을 배열에 저장합니다.
2. cache[idx][weight] = 배열의 idx 인덱스 이후의 물품들을 사용해서 weight 무게 내로 가질 수 있는 최대 가치입니다.
3. idx를 하나씩 늘려가며 현재 물품을 가방에 넣을 때와, 넣지 않을 때 중 가치가 높은 것을 cache 배열에 저장합니다
4. 0번 인덱스부터 K의 무게로 시작하는 메모이제이션 함수를 출력합니다

---

⌨️ 코드

public class _12865_평범한배낭 {
    static class Product {
        int v, w;

        public Product(int w, int v) {
            this.v = v;
            this.w = w;
        }
    }
    static int N, K;
    static Product[] Products;
    static int[][] cache;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        Products = new Product[N];
        cache = new int[N][K + 1];
        for(int i = 0; i < N; i++)
            Arrays.fill(cache[i], -1);
        for(int i = 0; i < N; i++)
        Products[i] = new Product(sc.nextInt(), sc.nextInt());
        System.out.println(solve(0, K));
    }

    public static int solve(int idx, int weight) {
        if(idx == N) return 0;
        int ret = cache\[idx\][weight];
        if(ret != -1) return ret;
        ret = solve(idx + 1, weight);
        if(weight >= Products[idx].w)
            ret = Math.max(ret, solve(idx + 1, weight - Products[idx].w) + Products[idx].v);
        return cache\[idx\][weight] = ret;
    }
}

---

📋 결과