[백준] 12865번 - 평범한 배낭 (Gold 5)

문제 링크

백준 12865번 - 평범한 배낭 (Gold 5)

문제 설명

물건들의 무게와 가치, 배낭의 최대 무게가 주어져 있다.
배낭의 무게 제한을 넘기지 않으면서 최대한의 가치를 가지도록 물건을 담는다.
이 때 가능한 최대 가치를 구하는 문제이다.

정답 코드 및 설명

유명한 배낭 문제이다. DP로 푸는 전형적인 문제이다.
특정 물건을 담는 경우와 담지 않는 경우로 나누어서 점화식을 세우면 쉽게 풀 수 있다.

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

public class Main {

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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        Stuff stuffs[] = new Stuff[N];
        int weight, value;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            weight = Integer.parseInt(st.nextToken());
            value = Integer.parseInt(st.nextToken());
            stuffs[i] = new Stuff(weight, value);
        }
        Arrays.sort(stuffs);

        int w, v, temp[];
        int bag[] = new int[K + 1];
        for (int i = 1; i <= N; i++) {
            w = stuffs[i - 1].weight;
            v = stuffs[i - 1].value;
            temp = bag.clone();
            for (int j = w; j <= K; j++) {
                if (temp[j - w] + v > bag[j])
                    bag[j] = temp[j - w] + v;
            }
        }
        bw.write(bag[K] + "");
        bw.close();
    }

}

class Stuff implements Comparable<Stuff> {
    int weight, value;

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

    public int compareTo(Stuff s) {
        return this.weight - s.weight;
    }
}