[백준] 12865번 배낭 문제

백준 12865번 배낭문제 링크

문제 요약

대표적인 dp문제 중 하나인 배낭문제(knapsack problem)를 풀어보았다.
dp문제는 최적성 원리를 만족해야한다. 최적성의 원리란 주어진 문제의 최적해가 분할된 부분문제의 최적해로 구성됨을 의미한다.
배낭 문제는 주어진 여러 개의 아이템들 중에서 어떤 아이템을 배낭에 담아야 weight limit 내에서 가장 높은 value를 담을 수 있을 지 해결하는 문제이다.
주어진 무게에서 각 아이템에 대해서 해당 아이템을 담지 않았을 때의 최적해와 담았을 때의 최적해를 비교하여 더 큰 값을 취한다면 최적해를 보장할 수 있다.

---

코드

import java.io.*;
import java.util.*;
public class Main{
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] datas = br.readLine().split(" ");
        int N = Integer.parseInt(datas[0]);
        Item[] items = new Item[N];
        int W = Integer.parseInt(datas[1]);
        for (int i = 0 ; i < N ; i++)
        {
            String[] weightAndValue = br.readLine().split(" ");
            items[i] = new Item(Integer.parseInt(weightAndValue[0]), Integer.parseInt(weightAndValue[1]));
        }
        dp = new int[N+1][W+1];
        int max = -1;
        for (int i = 1; i <= N ; i++)
        {
            Item current = items[i-1];
            for (int j = 0; j <= W ; j++)
            {
                if (current.weight > j) {
                    dp[i][j] = dp[i - 1][j];
                }
                else {
                    dp[i][j] = Math.max(current.value + dp[i-1][j-current.weight], dp[i-1][j]);
                }
            }
            if (dp[i][W] > max)
                max = dp[i][W];
        }
        System.out.println(max);
    }
}

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

---

문제 해결 방법

1. dp[N+1][W+1]의 2차원 배열을 선언한다.
2. 받은 아이템들을 하나씩 배낭에 넣어보는데, 무게가 1일 때부터 배낭의 한계 무게까지 무게를 1씩 올려가면서 해당 무게에서 최대로 담을 수 있는 value를 계산한다.

value 계산 방법은 다음과 같다.
1) 만약 현재 계산 중인 무게(w)가 넣으려고 하는 아이템의 무게보다 작다면 아이템을 넣을 수 없으므로 이전 아이템에서 계산한 최적값을 그대로 가져온다.(dp[i][w] = dp[i-1][w])

2) w가 current item의 weight보다 크거나 같다면 아이템을 배낭에 넣어보는 것을 고려할 수 있다. 이 때 배낭에 현재 아이템을 넣었을 때의 value 합과 넣지 않았을 때 value합을 비교하여 더 큰 값을 dp[i][w]에 저장한다.

3) 배낭에 current item을 넣기 위해선 current item의 무게만큼을 배낭에서 비워야하고 이 때 배낭 value의 최대값은 dp[i-1][w-currentItem.weight]에 저장되어 있다. 따라서 dp[i-1][w-currentItem.weight] + currentItem.value(현재 아이템을 넣었을 때)와 dp[i-1][w](현재 아이템을 넣지 않았을 때)를 비교하여 더 큰 값을 dp[i][w]에 넣으면 문제의 조건을 만족하는 점화식이 완성된다.

위의 방식으로 문제를 해결한다면 시간복잡도는 O(NW)이다.