PACKING 여행 짐 싸기 / ALGOSPOT

• 문제링크 : https://algospot.com/judge/problem/read/PACKING
• 제출링크 : https://algospot.com/judge/submission/detail/656203
• 자바코드 : https://github.com/skysign/WSAPT/blob/master/ALGOSPOT/PACKING/src/Main.java

유명한 문제인 Knapsack 문제에서, 아이템이 목록을 출력하는 부분이 추가된 문제입니다.
Knapsack문제가 처음이신 분들은 atcoder.jp의 educational DP 문제 중에 D - Knapsack 1 먼저 풀어보시는 것을 추천합니다. 해당 문제의 풀이는 D - Knapsack 1 풀이 여기를 참고하세요.
참고로, D - Knapsack 1 풀이에서는 DP를 recursion으로 하지 않고, 이중루프로 구현했습니다. 이번 문제에서는 recursion으로 코딩했습니다.

PACKING문제도, 최대 절박도의 합을 구하는 방법은 D - Knapsack 1와 동일합니다.
다만, 책의 코드 9.2에서는 재귀함수로 구현이 되어 있구요, 저의 D - Knapsack 1풀이에서는 이중루프로 구현되어 있습니다.
속도는 메모이제이션을 활용한 책의 코드가 빠를 것이구요. 저때는 Problem Solving 자체에 대해서 너무 모르고,
점화식을 코딩하는 것에 중점을 두다 보니, 이중루프로 구현한 것 같습니다.

다시 PACKING문제로 돌아와서, 책의 코드 9.3에서 reconstruct()를 콜하기 전에, cache[][]에 결과가 저장이 되어 있기 때문에, reconstruct()함수 안에서 pack()을 호출 해도, 실행시간이 아주 조금 늘 뿐입니다.

책에서는 코드 9.3에 대한 설명이 부족한 것 같아서, 이부분을 좀더 설명하겠습니다.

dp_{i,j} 라고 하구요, 책에서는 cache로 코딩되어 있는 부분이, 이 글에서는 dp 입니다.
i 가 아이템 번호, j 가 절박도, J는 각 아이템의 절박도 리스트로 가정합니다.
코드 9.2를 설명하는 부분에서 'pack(capacity, item+1)과 pack(capacity, item)이 같은지 비교하면 됩니다.' 라고 적혀 있는대요. 이부분을 좀 풀어 보면...

\begin{aligned}
dp_{i,j} = max(dp_{i+1,j}, dp_{i,j} + J_j) \\
\end{aligned}

위와 같이 dp_{i,j}는 2가지 값중에 최대값을 선택하게 됩니다.
코드에 보면 dp_{i,j}와 dp_{i+1,j}가 같은지 확인하고, 같으면, i 아이템이 선택되지 않은 것으로 판단합니다.
\begin{aligned}
dp_{i,j} == dp_{i+1,j} \\
\end{aligned}
위의 식이 참이라는 의미는, dp_{i,j} + J_j < dp_{i+1,j} 이 성립하므로, dp_{i,j}에서도 i 번째 아이템을 제외 했을 때, 절박도의 최대값을 얻을 수 있었다는 의미가 됩니다.

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
 * PACKING 여행 짐 싸기 / ALGOSPOT
 * 문제링크 : https://algospot.com/judge/problem/read/PACKING
 * 제출링크 : https://algospot.com/judge/submission/detail/656203
 */

public class Main {
    int N;
    int W;
    int[] Ws;
    int[] Vs;
    String[] Ss;
    int[][] dp;
    ArrayList<String> al;

    public void solve() throws IOException {
        int T = sc.nextInt();

        for(int t=0; t<T; ++t) {
            int r = 0;
            N = sc.nextInt();
            W = sc.nextInt();
            Ws = new int[N];
            Vs = new int[N];
            Ss = new String[N];
            dp = new int[N][W+1];
            al = new ArrayList();
            fill2D(dp, -1);

            for(int i=0; i<N; ++i) {
                String strT = sc.nextLine();
                String[] Ts = strT.split(" ");
                Ss[i] = Ts[0];
                Ws[i] = Integer.parseInt(Ts[1]);
                Vs[i] = Integer.parseInt(Ts[2]);
            }

            r = knapsack(W, 0);
            reconstruct(W, 0);
            println(r + " " + al.size());
            for(String s: al)
                println(s);
        }
    }

    public int knapsack(int w, int idx) {
        if(idx == N)
            return 0;

        if(dp[idx][w] != -1)
            return dp[idx][w];

        int r1 = knapsack(w, idx+1);
        int r2 = 0;

        if(w-Ws[idx] >= 0)
            r2 = knapsack(w-Ws[idx], idx+1) + Vs[idx];

        return dp[idx][w] = Math.max(r1, r2);
    }

    public void reconstruct(int w, int idx) {
        if(idx == N)
            return;

        if(knapsack(w, idx) == knapsack(w, idx+1)) {
            reconstruct(w, idx+1);
        }
        else{
            al.add(Ss[idx]);
            reconstruct(w-Ws[idx], idx+1);
        }
    }

    public void _solve() throws IOException {
        solve();
        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main._solve();
    }

    public void println(int a) throws IOException {
        bw.write(a);
    }

    public void println(long a) throws IOException {
        println(a+"");
    }

    public void println(String s) throws IOException {
        bw.write(s+"\n");
    }

    // 4 ways
    public int[] d4i = new int[]{-1, 1, 0, 0};
    public int[] d4j = new int[]{0, 0, -1, 1};
    // 8 ways
    public int[] d8i = new int[]{-1, 1, 0, 0,  -1, -1, 1, 1};
    public int[] d8j = new int[]{0, 0, -1, 1,  -1, 1, 1, -1};

    // Initialize 2D arrays with value v
    public void fill2D(int[][] _2D, int v) {
        for(int[] _1D: _2D) {
            Arrays.fill(_1D, v);
        }
    }

    // Initialize 3D arrays with value v
    public void fill3D(int[][][] _3D, int v) {
        for(int[][] _2D: _3D) {
            for(int[] _1D: _2D) {
                Arrays.fill(_1D, v);
            }
        }
    }

    // GCD
    int GCD(int a, int b) {
        if(0 == b) {
            return a;
        }

        return GCD(b, a%b);
    }

    long GCD(long a, long b) {
        if(0 == b) {
            return a;
        }

        return GCD(b, a%b);
    }

    public Reader sc = new Reader();
//    Sometimes, Reader class cause unknown problem, when I submit my java code.
//    For more detail, please see https://algospot.com/forum/read/4731/
//    public Scanner sc = new Scanner(System.in);

    public BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    // https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/
    public class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String nextLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
}