[문제해결을 위한 창의적 알고리즘] 배낭 문제 (고급 p.107)

책에도 설명되어 있듯이 이 문제는 굉장히 잘 알려진 문제이다. 그러나, 처음 접하는 사람들에게 특히 동적 계획법 (Dynamic Programming)으로 푸는 방법은 낯설게 느껴질 수 있다. 책에 굉장히 깔끔하고 간결한 풀이가 소개되어 있어서 그 코드를 자바로 작성해 보았다. 약간 해설이 부족한 점이 있는 것 같아 보충 설명을 더하였다.

DT[i][j]의 정의

1) i는 물건 번호

2) j는 주어진 무게

3) DT[i][j]는 i번째까지 물건까지 고려했을 때 (풀이에서는 n번째부터 거꾸로 계산하고 있음 유의), j 무게가 남아 있다면 가질 수 있는 최대 가치

풀이와 더불어 실제 테이블에 어떤 값이 쓰여지고 있는지 보면 이해가 좀 더 쉬울 것 같다. 

예제 입력:

4 5

2 3

1 2

3 3

2 2

정답:

7

테이블 데이타:

0 2 3 5 5 7 

0 2 2 4 5 5 

0 0 2 3 3 5 

0 0 2 2 2 2 

import java.util.Scanner;

public class KnapsackSol111 {

public static int[][] DT=new int[101][10001];

public static int[] W = new int[101];

public static int[] V= new int[101];

public static int max(int a, int b) {

return a > b ? a : b;

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int w = sc.nextInt();

for (int i = 1; i <=n; i++){

W[i]=sc.nextInt();

V[i]=sc.nextInt();

}

sc.close();

// n번째 물건부터 첫번째 물건까지 진행하면서, 남은 무게가 해당 물건의 무게보다 크지 않으면 이전 물건의 무게에 해당하는 최대 가치 가져옴

// 만약 남은 무게가 더 많다면 이전 무게에서 자신의 무게를 뺀 값을 테이블에서 조회해 보고 더 큰 값으로 업데이트 

for (int i =n; i >0; i--){

for (int j = 0; j <=w; j++){

if (j<W[i])

DT[i][j]=DT[i+1][j];

else

DT[i][j]=max(DT[i+1][j], DT[i+1][j-W[i]]+V[i]);

}

}

System.out.println(DT[1][w]);

/*

for (int i =1; i <=n;i++){

for (int j =0; j<=w; j++)

System.out.print(DT[i][j]+" ");

System.out.println("");

}

*/

return;

}

}

Big O(n*w) : n은 물건 수, w는 무게

Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/KnapsackSol111.java

문제해결을 위한 창의적 알고리즘 목록