ALGOSPOT
PACKING 여행 짐 싸기 / ALGOSPOT
건이두
2020. 2. 9. 12:00
728x90
- 문제링크 : 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();
}
}
}728x90