백준12865번 : 평범한 배낭

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class 백준12865_평범한배낭 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st = null;

    public static void main(String[] args) throws IOException{
        int n, k;
        int weight, value;
        int[][] backpack;
        ArrayList<Stuff> stuffs = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        backpack = new int[n + 1][k + 1];

        for (int i = 0; i < n; i++)
        {
            st = new StringTokenizer(br.readLine());
            weight = Integer.parseInt(st.nextToken());
            value = Integer.parseInt(st.nextToken());
            stuffs.add(new Stuff(weight, value));
        }
        Collections.sort(stuffs);

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= k; j++)
            {
                Stuff t = stuffs.get(i - 1);
                if (t.weight > j)
                {
                    backpack[i][j] = backpack[i - 1][j];
                }
                else
                {
                    backpack[i][j] = Math.max(backpack[i - 1][j], t.value + backpack[i - 1][j - t.weight]);
                }
            }
        }
        System.out.println(backpack[n][k]);
    }

    public static class Stuff implements Comparable<Stuff>{
        int weight;
        int value;

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

        @Override
        public int compareTo(Stuff o) {
            int cmp = Integer.compare(weight, o.weight);
            if (cmp == 0)
                return (Integer.compare(value, o.value));
            else
                return (cmp);
        }
    }
}

가장 기초 dp 문제며, knapsack problem 이라고 치면 많은 해설을 찾을 수 있다.

포인트는 다음과 같다.

물건 번호	물건 무게	물건 가치
1	3	6
2	4	8
3	5	12
4	6	13

주어진 물건들의 무게와 가치는 다음과 같다고 가정한다.

만약 가방의 무게가 7이라는 값으로 주어지게 되면 초기 값은 다음과 같다.

물건 번호 \ 가방 무게	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1
2
3
4

반복문으로 보게 된다면 1번행, 1번열부터 채우기 시작한다고 보면 된다.

점화식은 다음과 같다.

아래 점화식에서 사용할 stuff는 물건을 지칭하고, dp는 위 표를 가르킨다.

여기서 i는 행 ( 물건의 인덱스이자 표에서 행 )

여기서 j는 열 ( 가방의 무게이자, 표에서 열 )

i = 1, j = 1 부터 시작한다.

if stuff[i].무게 > j
  dp[i][j] = dp[i - 1][j];
else
  dp[i][j] = Math.max (dp[i - 1][j], stuff[i].가치 + dp[i - 1][j - stuff[i].무게])

설명보다 표의 값의 변화를 보는것이 이해가 빠를듯하다.

물건 번호 \ 가방 무게	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1 ( 무게 3 , 가치 6 )	0	0	6	6	6	6	6
2 ( 무게 4, 가치 8 )
3 ( 무게 5, 가치 12 )
4 ( 무게 6, 가치 13 )

i = 1, j = 1 일때, 위의 조건으로 비교해보면 1번 물건의 무게는 3 , 현재 가방 허용 무게는 j 즉 1이기때문에 if 문에서 true , 표의 (1, 1)은 (0, 1)의 값인 0

..... 쭉 가다가 j 가 3인 시점에 되면?

i = 1, j = 3 일때, 조건식 3 > 3 이 false가 되고 Math.max ( 0, 6 + 0 ) 이므로 6이 된다.

i = 2일때 보자.

물건 번호 \ 가방 무게	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1 ( 무게 3 , 가치 6 )	0	0	6	6	6	6	6
2 ( 무게 4, 가치 8 )	0	0	6	8	8	8	14
3 ( 무게 5, 가치 12 )
4 ( 무게 6, 가치 13 )

표에서 ( 2, 4 )를 봤을때 값이 8로 변한다. 단순하게 생각해서 가방 무게 제한까지 하나씩 증가시키면서 가장 높은 가치가 있는 물건을 넣는 행위를 끝까지 반복하는 것임.