[백준 BOJ 12865번] 평범한 배낭

출처 : https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

1. 문제

 

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

---

2. 입력

 

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

 

4 7
6 13
4 8
3 6
5 12

---

3. 출력

 

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

 

14

---

4. 풀이

일단 0/1 knapsack 문제이기 때문에 한 물건을 쪼개지 못하고 그대로 담아야 한다. 우선 dp[i][j]에서 j 무게만큼 채울 수 있을 때, 1~i번째 물건들을 가지고서만 만든 최적의 해이다.

 

<Top-Down 방식>

 

만약 i가 0 이하면 채울거리가 없기에 0을 리턴하고, k=0일 경우에는 알아서 dp[0][0]까지 내려오기 때문에 dp[0][0]만 0으로 설정해두면 된다. 만약 i가 0보다 크다면 그때부턴 dp값이 있으면 그대로 출력하고, 아니라면 i번째 물건보다 가방용량이 작다면 i-1번째에 담을 수 있었던 경우를 dp에 쓰고, 가방용량이 더 크다면 i번째 이전까지 현 무게에 넣을 수 있는 최적의 해(knapsack[i-1][j])와 지금 물건을 담고나서 이전의 물건들에 대해 최적의 해를 현 물건의 가치와 더한 값(knapsack[i-1][j-w[i]]+v[i])을 비교한 후 큰 값을 dp에 쓴다. 

 

<Bottom-Up 방식>

 

Top-Down방식과 똑같으나 이중 for문을 이용해서 dp값들을 채워 나간다.

---

5. 소스코드

<Top-Down 방식>

 

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

public class Main {
    static int N;
    static int K;
    static int [] w;
    static int [] v;
    
    static Integer [][] dp;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        w = new int [N+1];
        v = new int [N+1];

        for(int i=1; i<=N; i++){
            st = new StringTokenizer(br.readLine(), " ");
            w[i] = Integer.parseInt(st.nextToken());
            v[i] = Integer.parseInt(st.nextToken());
        }

        dp = new Integer [N+1][K+1];

        System.out.println(knapsack(N, K));
    }

    public static int knapsack(int i, int k){
        if(i <= 0){
            return 0;
        }
        
        else{
            if(dp[i][k] == null){
                if(w[i] > k)
                    dp[i][k] = knapsack(i-1, k);
                else{
                    dp[i][k] = (int)Math.max(knapsack(i-1, k), knapsack(i-1, k-w[i])+v[i]);
                }
            }
        }
        return dp[i][k];
    }
}

 

<Bottom-Down 방식>

 

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

public class Main {
    static int N;
    static int K;
    static int [] w;
    static int [] v;
    
    static int [][] dp;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        w = new int [N+1];
        v = new int [N+1];

        for(int i=1; i<=N; i++){
            st = new StringTokenizer(br.readLine(), " ");
            w[i] = Integer.parseInt(st.nextToken());
            v[i] = Integer.parseInt(st.nextToken());
        }

        dp = new int [N+1][K+1];
        
        for(int i=1; i<=N; i++){
            for(int j=1; j<=K; j++){
                dp[i][j] = 0;
                if(w[i] > j) dp[i][j] = dp[i-1][j];

                else{
                    dp[i][j] = (int)Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
                }
            }
        }
        
        System.out.println(dp[N][K]);
    }
}

---

6. 배운 것

일단, 처음에 문제를 잘못 이해했었다. 0/1 knapsack 문제로만 이해를 하고 주어진 물건들이 (1종류-1개씩) 이란걸 인지하지 못한 채 풀이한지라 다음 부분에서 i-1을 이해하지 못했었다.

else{
                    dp[i][k] = (int)Math.max(knapsack(i-1, k), knapsack(i-1, k-w[i])+v[i]);

knapsack 문제의 조건에서 만약 종류당 1개씩만이란 조건이 없다면 i-1만 i로 바꿔주어서 중복사용하는 방식의 결과도 도출할 수 있다.

 

이 문제에서의 Top-Down 방식이 사실상 DP문제를 푸는데에 있어서 찐 Top-Down 방식이라고 볼 수 있다.