[DP]Knapsack

Knapsack

배낭 문제

DP가 사용되는 문제 중 배낭문제는, 무제 제한이 K인 배낭에 무게와 가치가 정해진 N개의 물건이 있을 때 가치의 총합이 가장 크도록 배낭을 싸는 문제이다.

i : 현재 넣을지 고민하는 물건 번호

D :  배낭의 가치, 

V : 물건의 가치

문제를 해결하는 핵심은 각 물건이 배낭에 있는 경우와 없는 경우를 따지는 것이다.

이를 다음과 같은 점화식으로 표현한다.

D[i][j] = Max( D[i-1][j] , D[i-1][j-W[i]]+V[i] )

//배낭의 가치 = Max(i번 물건을 넣지 않는 경우, i번 물건을 넣는 경우) 

아래와 같은 예시가 있을 때, 알고리즘은 다음과 같은 순서로 진행 된다.

---

1번 물건을 넣으면, 배낭의 가치(D)는 13(V[i])만큼 더해지고, 무게제한 7에서 6(W[i])만큼 차지한다.

⇒ D[i-1][j-W[i]]+V[i] ⇒ D[0][1]+13 = 13

이 경우 무게제한으로 j ≥6 부터 담을 수 있다.

1번 물건을 넣지 않는 경우, 배낭의 가치와 무게는 이전 배낭과 같다.

⇒ D[i-1][j] ⇒ D[0][7] = 0

물건을 넣지 않은 경우와 넣는 경우를 비교해서 배낭의 가치를 계산한다.

…이를 반복하면, 배낭의 가치에 대한 배열 (D)가 완성되고, 마지막 물건까지 확인한 D[N][K]가 가장 비싼 물건을 무게 제한에 맞춰서 가져가는 경우가 된다. 세로 : 물건, 가로 : 무게제한

만약 이해가 되지 않는다면, “무게제한이 유동적이다” 라고 생각하면 편할 듯 하다. 배낭의 무게제한이 j일 때 담을 수 있는지 확인하고, 만약 담는다면, 제한에서 해당 무게를 뺀 배낭에서 이전 물건을 담은 경우 가치를 더한다. 즉, 3번 물건을 무게제한 7인 배낭에 담는 경우 가치는 6만큼 증가하고, 무게가 무게가 7-3=4만큼 남았기 때문에 이전 물건들 중 무게 제한이 4일 때 가치를 더하면 된다. D[3-1][7-3] = D[2][4] 를 더하면 14가 된다.

배열의 i-1이 있기 때문에 i는 1부터 시작하고, j>W[i]이란 조건문을 통해 물건을 넣을지 말지를 선택해야한다.

JAVA

---

...
int[] V; //물건의 가치 배열
int[] W; //물건의 무게 배열
int[][] D; //각 물건에 대한 경우의 가치, 초기값은 전부 0

...
for(int i=1; i<=N; i++) {
	for(int j=1; j<=K; j++) {
		if(j<W[i]){D[i][j] = D[i-1][j];}
		else{
			D[i][j] = Math.max( D[i-1][j], D[i-1][j-W[i]]+V[i])
		}
	}
}
System.out.println(D[N][K]);

추천문제

---

12865번: 평범한 배낭