백준 - 12865 평범한 배낭 - Java

백준 평범한 배낭 문제를 풀어보았다. 기본 문제라곤 하지만 처음 풀다 보니 풀이를 기억해둬야 할 것 같아 정리한다.

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

12865번: 평범한 배낭

풀이 시간: 1시간

---

문제 설명

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

준서가 여행을 가기 전 N개의 물건을 배낭에 담아 갈 생각이다.

각 물건은 무게 W, 가치 V를 가지며 버틸 수 있는 무게 K에 가치 V가 최대가 되게 꽉꽉 담으면 된다.

 

물건의 개수가 1 ~ 100이므로 O(N^2)도 가능

---

문제 풀이

 

1. 처음 생각한 아이디어는 간단하다 모든 물건에 대한 조합으로 완전탐색하면 된다. 하지만 이 경우는 2^N으로 시간 초과가 날 것이다.
2. 2^N이 아닌 방법을 더 최적화하여 축소시켜야 하기 때문에 현재까지 담은 물건이 최대의 가치를 나타내고, 그 상황에서 또 최대의 가치를 창출할 수 있도록 물건을 담으면 된다 -> DP 방식을 생각할 수 있다.

예제 그려보기

dp[i][j] => i번째 물건에 대해서 담을지 말지 현재까지 가능한 무게는 j일 때 가치가 값으로 들어감

i번째 물건\무게	1	2	3	4	5	6	7
1	0	0	0	6	8	13	13
2	0	0	0	8	8	13	13
3	0	0	6	8	8	13	14
4	0	0	6	8	12	13	14

• 먼저 주황색을 보자
  • 무게가 3까지 될 때 4번 물건에 대해서는 담지 않고(무게가 5니까) 3번 물건을 담고 있을 때가 최대이므로 6이 된다.
• 빨간색을 보자
  • 무게가 7까지 가능할 때 두 번째 물건을 담을 때를 보면 두 번째 물건은 무게가 4이다 따라서, 무게가 4짜리를 넣으려면 현재 무게 7 - 4를 한 3이고, 두 번째 물건을 넣기전인 dp[1][3]와 두 번째 물건을 넣었을 때의 값을 더 해 이전 dp[1][7]과 비교하고 최댓값을 넣어야 한다.
• 파란색을 보자
  • 세 번째 물건을 넣을지 말지를 선택하는 데, 최대 무게가 7이고, 세 번째 물건의 무게가 3이니까 무게가 4일 때, 세 번째 물건을 넣기전 -> dp[2][4] + v[3] 과 dp[2][7](세 번째 물건을 안 넣었을 때 최댓값)을 비교하여 큰 값을 넣는다.  

---

풀이 코드

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

class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()), k = Integer.parseInt(st.nextToken());
        int[][] dp = new int[n+1][k+1];
        int[] w = new int[n+1];
        int[] 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());
        }
        for(int i=1; i<=k; i++){    // 무게 i
            for(int j=1; j<=n; j++){    // 물건 j
                dp[j][i] = dp[j-1][i];  // 물건을 담지 못하면 이전 값이 최대임
                if(i - w[j] >= 0){    // 담을 수 있는 물건인지 체크
                    // 이 물건을 넣지 않았을 때 vs 물건을 넣었을 때(꽉 맞게)
                    dp[j][i] = Math.max(dp[j-1][i], dp[j-1][i - w[j]]+v[j]);
                }
            }
        }
        System.out.println(dp[n][k]+"");
        br.close();
    }
}

• if(i-w[j]>=0)
  • 현재 최대 무게가 i이고, 이번 차례에 담거나 담지 않을 물건의 무게 w[j] 당연히 i가 w[j]보다 크거나 같아야 담을 수 있다.
• dp[j][i] = Math.max(dp[j-1][i], dp[j-1][i - w[j]]+v[j]);
  • 이번 물건을 담지 않고 최대 무게가 i일 때 vs 최대 무게가 i이고, 이번 물건을 담았을 때 j-1(현재 물건 이전 꺼)        i - w[j](최대 무게가 이번 물건을 넣기 전) 일 때 최댓값 + 이번 물건의 가치 

---

쪼갤 수 없는 배낭문제를 0/1 Knapsack Problem, 쪼갤 수 있는 배낭문제를 Fraction Knapsack Problem라고 하는데, 쪼갤 수 있는 배낭 문제를 알고리즘 수업 때 배웠던 것 같다.. 힙정렬을 이용해 어떻게 했던 것 같은데 기억이 나질 않는다.. 다시 찾아서 풀어봐야겠다. 워낙 대표적인 알고리즘이라 ㅎㅎ..