아주 유 명한 배낭 문제이다.
해당 블로그에서 인사이트를 얻었다.
기존에 배낭문제를 접했을 때는 물건을 나눌 수 있었다. 그렇기에 그리디 알고리즘을 활용해 PriorityQueue 를 통해서 해결 했던 것 같다.
하지만, 물건을 쪼갤 수 없는 경우는 0/1 Knapsack Problem 라고 하며, DP를 사용해야 한다.
물건을 넣는다. 뺀다. 라는 2개의 선택지 밖에 없기 때문이다.
주어진 예제처럼 (Wi, Vi) = (6, 13), (4, 8), (3, 6), (5, 12) 이 주어졌을 때,
i/j 1 2 3 4 5 6 7
1 0 0 0 0 0 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 14dp 배열은 다음과 같이 구성될 수 있다.
dp 배열은 배낭의 무게가 j 일때 최대 가치를 나타낸 것이다.
그렇기에 j=3 일때 부터 물건이 들어갈 수 있고, 누적합 개념으로 이전 누적값에 영향을 받는다.
개인적으로 Top-Down 방식의 재귀함수는 익숙하지 않기 때문에, Bottom-Up 을 선호한다.
그렇기에 해결하기 위해서는 2개의 조건으로 분기될 수 있다.
- 선택된 물건을 배낭에 넣을 수 없다면 -> 이전까지의 물건들만으로 최대 가치를 계산
- 선택된 물건을 배낭에 넣을 수 있다면 -> 현재 물건을 넣기 전에 남은 용량으로 이전 물건들로부터 얻을 수 있는 최대 가치 + 현재 물건의 가치 와 이전 물건들만으로의 최대 가치 중 큰 값
1번은 쉽게 이해가 될 것이다. 코드로 나타내면 dp[i][j] = dp[i-1][j]
2번의 경우는 dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight]+value) 이런 식으로 표현할 수 있다.
예를 들어보면 무게(j)가 7일 때 i=3 번째 물건을 넣으려고 할때,
i 번째 무게는 3이기 때문에 선택된 배낭에 물건을 넣을 수 있다.
그렇다면 이전 값인 13과
7-3=4, j=4 번째 i-1 번째 값인 8과 i번째 가치 6을 더한 14 중 큰 값인 14를 선택하게 되는 것이다.
여기서 dp 배열을 1차원 배열로 구할 수 있는 방법이 존재한다.
우리가 각 탐색의 경우 i번째 물건에 대하여 무게의 합이 K를 넘겨서는 안된다. 이는 거꾸로 말하면 K(최대무게) - 누적된 W값이 0보다 커야한다는 의미다.
for (int i = 1; i <= N; i++) {
// K부터 탐색하여 담을 수 있는 무게 한계치가 넘지 않을 때까지 반복
for (int j = K; j - product[i].weight >= 0; j--) {
dp[j] = Math.max(dp[j], dp[j - product[i].weight] + product[i].value);
}
}핵심은 역순 탐색 이다.
처음에 최종 결과는 dp[k] 번째로 가장 마지막에 존재하는 최대값을 구하는데 어떻게 역순 탐색으로 가능한걸까? 라는 생각이 들었다.
그렇기에 (Wi, Vi) = (6, 13), (4, 8), (3, 6), (5, 12) 위의 예제를 적용시켜보기로했다.
i는 순차적으로 탐색하기에
물건 1: (무게 6, 가치 13)
j = 7: dp[7] = max(dp[7], dp[1] + 13) = max(0, 0 + 13) = 13
j = 6: dp[6] = max(dp[6], dp[0] + 13) = max(0, 0 + 13) = 13
결과: dp = [0, 0, 0, 0, 0, 0, 13, 13]물건 2: (무게 4, 가치 8)
j = 7: dp[7] = max(dp[7], dp[3] + 8) = max(13, 0 + 8) = 13
j = 6: dp[6] = max(dp[6], dp[2] + 8) = max(13, 0 + 8) = 13
j = 5: dp[5] = max(dp[5], dp[1] + 8) = max(0, 0 + 8) = 8
j = 4: dp[4] = max(dp[4], dp[0] + 8) = max(0, 0 + 8) = 8
결과: dp = [0, 0, 0, 0, 8, 8, 13, 13]물건 3: (무게 3, 가치 6)
j = 7: dp[7] = max(dp[7], dp[4] + 6) = max(13, 8 + 6) = 14
j = 6: dp[6] = max(dp[6], dp[3] + 6) = max(13, 0 + 6) = 13
j = 5: dp[5] = max(dp[5], dp[2] + 6) = max(8, 0 + 6) = 8
j = 4: dp[4] = max(dp[4], dp[1] + 6) = max(8, 0 + 6) = 8
j = 3: dp[3] = max(dp[3], dp[0] + 6) = max(0, 0 + 6) = 6
결과: dp = [0, 0, 0, 6, 8, 8, 13, 14]3단계 정도만 진행해도 결과값이 나오는 것을 확인할 수 있었다.
발상의 전환이 메모리와 성능을 높일 수 있다는 것을 깨달을 수 있었다...
이런 생각은 코딩테스트 시에는 생각이 날 것 같지 않지만, 중요한 개념이기에 현재는 알고만 가는 개념으로 생각하면 될 것 같다.
코드
import java.io.*;
import java.util.*;
/*
2초, 512MB
---
유명한 배낭 문제
물건마다 무게와 가치를 가지는데, 가방에 넣을 수 있는 물건의 최대 가치를 구하면 됨
물건을 나눌 수 없기 때문에 DP로 접근해야 한다.
(6 13) (4 8) (3 6) (5 12)
k = 7
i/j 1 2 3 4 5 6 7
1 0 0 0 0 0 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
해당 dp 배열은 배낭의 무게가 j 일때 최대 가치를 나타낸 것이다.
우선적으로 각 dp 배열에서 i 일때 담을 수 있는지 없는지 체크.
담을 수 없다면 이전 dp[i-1][j] 의 값을 가져옴.
담을 수 있다면 이전 dp[i-1][j] 의 값과, dp[i-1][j-(i일때 무게)]+(i일때 가치) 의 최대값을 구하면된다.
j=7의 예시로 i=3 일때 Max(13,8+6) = 14 가 나오게 된다.
---
N(1 ≤ N ≤ 100) 물품 수
K(1 ≤ K ≤ 100,000) 배낭 무게
W(1 ≤ W ≤ 100,000) 물건 무게
V(0 ≤ V ≤ 1,000) 물건 가치
*/
class Product {
int weight;
int value;
public Product (int weight, int value) {
this.weight = weight;
this.value = value;
}
}
public class Main {
public static int n, k, result;
public static Product[] products;
public static int[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
products = new Product[n+1];
for (int i=1; i<=n; i++) {
st = new StringTokenizer(br.readLine());
int weight = Integer.parseInt(st.nextToken());
int value = Integer.parseInt(st.nextToken());
products[i] = new Product(weight, value);
}
dp = new int[n+1][k+1];
for (int i=1; i<=n; i++) {
for (int j=1; j<=k; j++) {
if (products[i].weight > j) { // 배낭에 넣을 수 없다면
dp[i][j] = dp[i-1][j];
}
else { // 배낭에 넣을 수 있다면
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-products[i].weight] + products[i].value);
}
}
}
System.out.println(dp[n][k]);
}
}
import java.io.*;
import java.util.*;
class Product {
int weight;
int value;
public Product (int weight, int value) {
this.weight = weight;
this.value = value;
}
}
public class Main {
public static int n, k, result;
public static Product[] products;
public static int[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
products = new Product[n+1];
for (int i=1; i<=n; i++) {
st = new StringTokenizer(br.readLine());
int weight = Integer.parseInt(st.nextToken());
int value = Integer.parseInt(st.nextToken());
products[i] = new Product(weight, value);
}
dp = new int[k+1];
for (int i=1; i<=n; i++) {
for (int j=k; j-products[i].weight >= 0; j--) {
dp[j] = Math.max(dp[j], dp[j - products[i].weight] + products[i].value);
}
}
System.out.println(dp[k]);
}
}
메모리와 시간 측면에서 더 월등한 모습을 보여준다!!
