문제
n개의 보석이 있다. 각 보석은 자신의 고유 무게와 가치가 있다. 배낭에 이 보석들을 담는데, 보석들의 가치 총계가 최대가 되게끔 담아라. 단, 배낭에 담을 수 있는 최대무게는 제한되어있다. 즉, 제한된 무게내에서 최대가치가 되게 보석들을 담아야 한다. (담을 수 있는 개수는 제한이 없다.)
입력
입력은, 처음에 문제 개수 T가 나오고, 그 다음 줄에 보석의 개수 N과 베낭에 담을 수 있는 최대 무게가 주어진다. 그 다음줄에는 N개의 보석에 대한 무게가 주어지고, 그 다음 줄에 N개 보석에 대한 가치가 주어진다.
ex) T=1, N=4, 최대무게=10, 무게={5,4,6,3}, 가치={10,40,30,50}
1
4 10
5 4 6 3
10 40 30 50
출력
최대가치를 가지도록 하려면, 어떤 보석을 담아야하고, 총 얼마만큼의 가치인지를 출력하시오.
(출력 예)
MaxValue=90
선택 번호 리스트:4 2
총 Weight:7
총 Value:90
---------------------------------------------------------------------------
*********************************************************************************************
---------------------------------------------------------------------------
[풀이]
다이나믹 프로그래밍으로 해결할 수 있는 대표적인 문제다.
해결할 수 있는 점화식을 생각해내는게 어렵고, 어떤 보석을 선택했는 지 트레이싱하는게 좀 까다롭다.
먼저, 점화식을 생각해내자.
점화식을 생각할 때는 항상 최종단부터 시작해야한다. 즉, 최종단에서 최대가치를 가지려면, 앞쪽에서 어떤 조건일 때일까?
보석번호(i)와 무게(w)를 인자로 가지면서, 가치를 나타내는 V라는 함수를 생각해 보자.
V(i,w) : 1~i까지 보석에 대해서, w무게까지 허용되었을 때 가지는 최대가치
그렇다면 V(i,w)는, 해당 i번째 보석을 담기전의 상태에서 i번째 보석을 담은 것이라고 할 수 있다. 즉, V(i,w) = V(i-1,w-wt[i]) + val[i].
과연 언제나 그럴까?
아니다. V(i-1,w)상태에서 그대로 V(i,w)가 되었을 수도 있다. (잘 생각해보자)
즉, (i-1)개 보석이 있는 상태가 V(i-1,w)라고 생각해보자. 이 상태에서, 무게가 wt[i]이고 가치가 val[i]인 보석을 하나 더 넣는 것이다. 마냥 넣을 수는 없다. 왜냐면 현재 허용가능한 무게인 w보다 wt[i]가 더 작아야 넣을 수 있는 것이다. 조건:w>=wt[i]
또한 i번째 보석을 넣어 무게가 w가 되었을 때의 가치가, 현재의 가치보다 더 커야한다. 조건:max( V(i,w), V(i-1,w-wt[i])+val[i] )
(이 부분이 잘 이해가 안되면, 아래쪽 실제 예제를 손으로 꼭 해보길 권장)
정리하면 V(i,w)는, 그냥 V(i-1,w)일 수도 있고, V(i,w-wt[i])+val[i] 일 수도 있다.
수식으로 쓰면 다음과 같이 될 것이다.
V(i,w) = (w >= wt[i]) ? max(V(i-1,w), V(i-1,w-wt[i]) + val[i]) : V(i-1,w)
이게 점화식의 전부이고, 배낭문제의 핵심 수식이다.
근데, 이렇게 설명듣고 수식을 눈으로만 보면, 사실 이 내용을 이해하기 힘들고, 코딩하기 힘들다. 손으로 한번 풀어 봐야한다. (배낭문제를 이해하려면 아래 전개되는 과정을 꼭 손으로 풀어보시길 권장)
간단한 예를 손으로 풀어보자.
4개 보석이 있고, 무게와 가치가 다음과 같을 때, 무게 10 이내에서 최대가치가 되게 보석을 선택해보자. (직관적으로 2번과 4번 보석을 선택해서, 가치가 90임을 알 수 있지만...^^)
번호(i) | 무게(wt) | 가치(val) |
1 | 5 | 10 |
2 | 4 | 40 |
3 | 6 | 30 |
4 | 3 | 50 |
시작은 번호가 가장 크고, 최대 무게인 10에서 출발한다. V(4,10): 1~4번까지 보석에 대해, 무게 10까지 허용되었을 때 최대 가치
V(i,w) = if(w >= wt[i]) max(V(i-1,w), V(i-1,w-wt[i])+val[i] )
else V(i-1,w)
V(4,10) = if(10 >= 3) max( V(3,10), V(3,10-3)+50 ) --> 이것을 계산하려면 V(3,10)과 V(3,7)을 알아야 한다.
V(3,10) = if(10 >= 6) max( V(2,10), V(2,10-6)+30 ) --> V(2,10) V(2,4) 필요
V(3,7) = if(7 >= 6) max( V(2,7), V(2,7-6)+30 ) --> V(2,7) V(2,1) 필요
V(2,10) = if(10 >=4) max( V(1,10), V(1,10-4)+40 )
V(2,4) = if(4 >= 4) max( V(1,4), V(1,4-4)+40 )
V(2,7) = if(7 >= 4) max( V(1,7), V(1,7-4)+40 )
V(2,1) = if(1 < 4) V(1,1)
V(1,10) = if(10 >= 5) max( V(0,10), V(0,10-5)+10 )
V(1,6) = if(6 >= 5) max( V(0,6), V(0,6-5)+10 )
V(1,7) = if(7 >= 5) max( V(0,7), V(0,7-5)+10 )
V(1,4) = if(4<5) V(0,4)
V(1,3) = if(3<5) V(0,3)
V(1,1) = if(1<5) V(0,1)
이제 베이스 조건을 생각해보면, V(0,x)=0 이다. 즉, 한개의 보석도 대상이 아니면, 가질 수 있는 가치는 zero
또한 V(x,0)=0이다. 허용된 무게가 없으면 마찬가지로 zero
따라서, V(1,10), V(1,6)등의 값을 구할 수 있다.
V(1,10) = if(10 >= 5) max( V(0,10), V(0,10-5)+10 ) = max(0, 0+10) = 10
V(1,6) = if(6 >= 5) max( V(0,6), V(0,6-5)+10 ) = max(0,10) = 10
V(1,7) = if(7 >= 5) max( V(0,7), V(0,7-5)+10 ) = max(0,10) = 10
V(1,4) = if(4<5) V(0,4) = 0
V(1,3) = if(3<5) V(0,3) = 0
V(1,1) = if(1<5) V(0,1) = 0
V(2,10) = if(10 >=4) max( V(1,10), V(1,10-4)+40 ) = max(10, 10+40) = 50
V(2,4) = if(4 >= 4) max( V(1,4), V(1,4-4)+40 ) = max(0,0+40) = 40
V(2,7) = if(7 >= 4) max( V(1,7), V(1,7-4)+40 ) = max(10,40) = 40
V(2,1) = if(1 < 4) V(1,1) = 0
3개 4일 때를 계속해서 구해보면
V(3,10) = if(10 >= 6) max( V(2,10), V(2,10-6)+30 ) = max(50, 40) = 50
V(3,7) = if(7 >= 6) max( V(2,7), V(2,7-6)+30 ) = max(40,0) = 40
V(4,10) = if(10 >= 3) max( V(3,10), V(3,10-3)+50 ) = max(50, 40+50) = 90
따라서, 원하는 답인, 보석 4개를 대상으로 했을 때, 무게 10이내에서 선택할 수 있는 최대가치인 90이 나왔다. !!
이제 어떤 보석을 선택했는지 알아내는 작업을 해보자.
테이블로 생각해보면 약각 쉽다.
위 과정에서 계산된 값을 테이블로 그려보면 다음과 같다.
이 테이블을 가지고 어떤 보석이 선택되어서 90이 되었는지 알아내면 된다.
방법은 다음과 같다.
먼저 V(4,10)일 때 값이 90에서 출발해보면,
위에서 손으로 계산한 루틴에서, 이 90이 되는 조건은 아래와 같았다.
V(4,10) = if(10 >= 3) max( V(3,10), V(3,10-3)+50 ) = max(50, 40+50) = 90
잘 살펴보면, V(4,10)과 V(3,10)을 비교했을 때, 같지 않으면 보석4가 선택됨을 알 수 있다.
보석4가 선택되었으므로 그 이전에 보석이 3개일때의 w 조건은 w-wt[i] = 10-3=7
즉, V(3,7)로 이동.
아래 그림으로 이 과정을 이해해 보자.
이 처럼, V 테이블이 만들어져 있으면, 어떤 보석을 선택하면 될지를 알 수 있다.
코드로 구현해보면 아래와 같을 것이다.
private static int[] extract(int[][] V, int W, int[] wt) {
ArrayList<Integer> list = new ArrayList<Integer>();
int K = W;
for (int i = V.length - 1; i >= 1; i--) {
if(K>=0 && V[i][K] != V[i-1][K]){
list.add(i);
K = K - wt[i];
}
}
int[] a = new int[list.size()];
for (int i = 0; i < a.length; i++) {
a[i] = list.get(i);
}
return a;
}
이제, 다시 처음으로 돌아가서, 처음부터 코드를 짜보자.
먼저, 점화식을 아래와 같이 만들었다.
V(i,w) = V(i-1,w) where w < wt[i]
max( V(i,w), V(i-1,w-wt[i])+val[i] ) where w >= wt[i]
이를 재귀호출을 이용해서 작성하면 다음과 같은 모습이 될 것이다.
private static int knap_recursive(int n, int w, int[] wt, int[] val) {
if (n <= 0 || w <= 0) {
return 0;
}
if (wt[n] > w) {
return knap_recursive(n - 1, w, wt, val);
} else {
return Math.max(knap_recursive(n - 1, w, wt, val),
knap_recursive(n - 1, w - wt[n], wt, val) + val[n]);
}
}
이렇게 하면 동작한다. 그러나 n과 w값이 커지면 거의 동작을 안한다. 중복 수행되는 것이 너무 많아서 실행시간이 무지 오래걸리기 때문이다.
따라서, 이미 계산된 값은 다시 계산되지 않도록 테이블에 저장하도록 하자. (메모이제이션)
다음과 같다.
private static int knap_table(int n, int w, int[] wt, int[] val, int[][] table) {
if (n <= 0 || w <= 0) {
return 0;
}
if ((n>1) && (table[n - 1][w] == 0)) {
table[n - 1][w] = knap_table(n - 1, w, wt, val, table);
}
if ((n>1 && w>wt[n]) && (table[n - 1][w - wt[n]] == 0)) {
table[n - 1][w - wt[n]] = knap_table(n - 1, w - wt[n], wt, val, table);
}
if ((wt[n] <= w) && (table[n - 1][w] < table[n - 1][w - wt[n]] + val[n])) {
table[n][w] = table[n - 1][w - wt[n]] + val[n];
} else {
table[n][w] = table[n - 1][w];
}
return table[n][w];
}
table값이 초기값인 0이면 계산하고, 아니면 그 값을 그냥 이용하도록 했다.
여기서 주의할 것은, 배열 인자값으로 음수가 들어가지 않도록 사전 조건을 넣어 둔 것.
if ((n>1) && (table[n - 1][w] == 0)) ...
if ((n>1 && w>wt[n]) && (table[n - 1][w - wt[n]] == 0)) ...
이 정도까지만 (table을 이용한 것) 해도, 충분하다. (in my opinion)
그러나, 아래와 같은 방법도 있다는 것을 알아두자.
private static int knapack_bottomup(int N, int W, int[] wt, int[] val, int[][] V) {
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= W; j++) {
if ((wt[i] <= j) && (V[i - 1][j] < val[i] + V[i - 1][j - wt[i]])) {
V[i][j] = val[i] + V[i - 1][j - wt[i]];
} else {
V[i][j] = V[i - 1][j];
}
}
}
return V[N][W];
}
knapsack_table()의 경우는, 점화식의 개념대로, 필요한 테이블 데이터만 top down으로 작성해나가는 방식인데 반해(테이블의 전체 데이터를 만들지 않음), knapack_bottomup()은, 테이블의 모든 데이터를 만들면서 결과를 얻어내는 방식이다.
두 방법의 속도를 비교해보면 비슷하다. knapsack_table()이 데이터를 덜 생성하지만, 데이터의 생성마다 메서드가 호출되는 속도저하 요인이 있고, knapsack_bottomup()이 데이터의 생성개수가 더 많지만(테이블 전체), 한 메서드 내에서 모든 계산이 이뤄지는 속도향상 요인이 있어, 서로 상쇄되어 속도가 비슷한 듯 하다.
knapsack 알고리즘을 소개한 자료들을 보면, 어떤 아이템이 선택되었는 지를 tracing하기 위해, 별도의 배열을 사용해서, 해당 보석이 선택될 때 1, 아닐 때 0을 저장해뒀다가, 이 별도 테이블을 분석해서 보석을 선택하는데, 여기서는 굳이 별도의 배열을 사용하지 않고, 메모이제이션을 위한 테이블만 이용해서 트레이싱을 했다. 더 효율적이라 생각한다.
[소스 코드]
package dynamic;
import java.io.File;
import java.util.ArrayList;
import java.util.Scanner;
public class Knapsack {
public static void main(String[] args) throws Exception {
long t1, t2;
Scanner sc = new Scanner(new File("res/knapsack.in"));
int T;
T = sc.nextInt();
int N = 0;
int W = 0;
int[] wt = null;
int[] val = null;
for (int testNum = 1; testNum <= T; testNum++) {
N = sc.nextInt(); // 개수
W = sc.nextInt(); // 최대 수용 무게
wt = new int[N + 1]; // 무게
for (int i = 1; i <= N; i++) {
wt[i] = sc.nextInt();
}
val = new int[N + 1]; // 가치
for (int i = 1; i <= N; i++) {
val[i] = sc.nextInt();
}
t1 = System.currentTimeMillis();
int maxValue = getMaxValue(N, W, wt, val);
t2 = System.currentTimeMillis();
System.out.println("MaxValue=" + maxValue + "(" + (t2 - t1) + "ms)");
int[] list = getMaxItems(N, W, wt, val);
printList(list, wt, val);
}
sc.close();
}
private static void printList(int[] list, int[] wt, int[] val) {
if (list == null || list.length == 0) {
System.out.println("fail");
return;
}
StringBuffer sb = new StringBuffer();
long totalWeight = 0;
long totalValue = 0;
for (int i = 0; i < list.length; i++) {
sb.append(list[i] + " ");
totalWeight += wt[list[i]];
totalValue += val[list[i]];
}
System.out.println("선택 번호 리스트:" + sb.toString());
System.out.println("총 Weight:" + totalWeight);
System.out.println("총 Value:" + totalValue);
System.out.println("");
}
private static int getMaxValue(int N, int W, int[] wt, int[] val) {
int[][] V = new int[N + 1][W + 1];
int max=0;
//max = knap_recursive(N, W, wt, val);
max = knap_table(N, W, wt, val, V);
//max = knapack_bottomup(N, W, wt, val, V);
// print(V);
return max;
}
private static int[] getMaxItems(int N, int W, int[] wt, int[] val) {
int[][] V = new int[N + 1][W + 1];
knap_table(N, W, wt, val, V);
//knapack_bottomup(N, W, wt, val, V);
return extract(V, W, wt);
}
private static int[] extract(int[][] V, int W, int[] wt) {
ArrayList<Integer> list = new ArrayList<Integer>();
int K = W;
for (int i = V.length - 1; i >= 1; i--) {
if(K>=0 && V[i][K] != V[i-1][K]){
list.add(i);
K = K - wt[i];
}
}
int[] a = new int[list.size()];
for (int i = 0; i < a.length; i++) {
a[i] = list.get(i);
}
return a;
}
private static void print(int[][] v) {
for (int i = 0; i < v.length; i++) {
for (int j = 0; j < v[i].length; j++) {
System.out.print(v[i][j] + " ");
}
System.out.println("");
}
}
// w: 현재기준으로 허용가능한(=더 담을 수 있는) 무게
private static int knap_recursive(int n, int w, int[] wt, int[] val) {
if (n <= 0 || w <= 0) {
return 0;
}
if (wt[n] > w) {
return knap_recursive(n - 1, w, wt, val);
} else {
return Math.max(knap_recursive(n - 1, w, wt, val),
knap_recursive(n - 1, w - wt[n], wt, val) + val[n]);
}
}
private static int knap_table(int n, int w, int[] wt, int[] val, int[][] table) {
if (n <= 0 || w <= 0) {
return 0;
}
if ((n>1) && (table[n - 1][w] == 0)) {
table[n - 1][w] = knap_table(n - 1, w, wt, val, table);
}
if ((n>1 && w>wt[n]) && (table[n - 1][w - wt[n]] == 0)) {
table[n - 1][w - wt[n]] = knap_table(n - 1, w - wt[n], wt, val, table);
}
if ((wt[n] <= w) && (table[n - 1][w] < table[n - 1][w - wt[n]] + val[n])) {
table[n][w] = table[n - 1][w - wt[n]] + val[n];
} else {
table[n][w] = table[n - 1][w];
}
return table[n][w];
}
private static int knapack_bottomup(int N, int W, int[] wt, int[] val, int[][] V) {
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= W; j++) {
if ((wt[i] <= j) && (V[i - 1][j] < val[i] + V[i - 1][j - wt[i]])) {
V[i][j] = val[i] + V[i - 1][j - wt[i]];
} else {
V[i][j] = V[i - 1][j];
}
}
}
return V[N][W];
}
static int max(int a, int b) {
return (a > b) ? a : b;
}
}
[입력 문제] kanpsack.in
6
4 10
5 4 6 3
10 40 30 50
3 30
5 10 20
50 60 140
3 50
10 20 30
60 100 120
5 20
2 3 4 5 9
3 4 5 8 10
30 60
2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9
3 4 5 8 10 4 6 11 2 20 3 4 5 8 10 4 6 11 2 20 3 4 5 8 10 4 6 11 2 20
40 80
2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9 2 3 4 5 9
3 4 5 8 10 4 6 11 2 20 3 4 5 8 10 4 6 11 2 20 3 4 5 8 10 4 6 11 2 20 3 4 5 8 10 4 6 11 2 20
-끝-
'알고리즘 > 알고리즘(Java)' 카테고리의 다른 글
| 24.[다이나믹]조립라인 스케줄링(Assembly Line Scheduling) (0) | 2015.04.25 |
|---|---|
| 23. [다이나믹]옷 (0) | 2015.04.24 |
| 21. [다이나믹] 최소 공정시간 찾기 (0) | 2015.04.21 |
| 20. [다이나믹] 행렬 경로 문제 (0) | 2015.04.16 |
| 19. [다이나믹]피보나치 수열 (0) | 2015.04.14 |