[문제해결을 위한 창의적 알고리즘] 배낭 문제 (고급 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