Dynamic Programming : Knapsack Problem

참고 문헌 :

chanhuiseok.github.io/posts/improve-6/#trending-tags

[알고리즘 트레이닝] 5장 - 동적계획법과 냅색(Knapsack) (백준 12865번 평범한 배낭 문제로 살펴보기)

gsmesie692.tistory.com/113

Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)

 

 

galid1.tistory.com/507

알고리즘 - Dynamic Programming(동적프로그래밍)이란?

 

---

1. Dynamic Programming 

1.1 정의 : 큰 문제를 작은 문제로 나누어서 문제를 해결합니다. (Ex) 피보나치수열

 

1.2 조건 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성해야 합니다. (최적성의 원리) 즉, 간단하게 작은 문제들이 반복하여 발생하는 경우 그때마다 작은 문제의 답이 바뀌지 않을 때 DP를 만족합니다.

---

2. Knapsack Problem

문제 설명 : 유명한 DP문제 중하 나입니다. 문제는 다음과 같습니다. N개의 물건의 무게(W)와 가치(V)를 주어지고 가방에 넣을 수 있는 최대 무게(K)가 주어질 때 가방에 넣을 수 있는 물건 들의 가치의 최대 값을 구할 때 사용합니다.

 

아이디어 : 첫 번째 물건부터 순차적으로 가방에 넣을 수 있는 최대 무게 1 ~ K에 대하여 최대 값을 가지고 있으면 n 번째 물건에 대하여 가방에 넣을 수 있는 최대 무게 1 ~ K에 대하여 최대 값은 다음과 같습니다.

 

1) n 번째 물건을 가방에 넣을 수 있을 때 :

넣는 경우 가방의 최대 가치 : n -1 번째 물건까지 진행한 데이터 중에서 넣은 물건의 무게 합이 K - Wn(n 번째 물건의 무게)인 데이터의 최대 V1(가치)

넣지 않을 때 가방의 최대 가치 : n - 1 번째 물건까지 진행한 데이터 중에서 넣은 물건의 무게 합이 K 인 데이터의 최대 V2(가치)

두 데이터를 가지고 V1 + Vn(n 번째 물건의 가치)과 V2를 비교하여 쉽게 n 번째 물건이 가방에 넣을 수 있는 최대 무게 K에 대하여 가방의 최대 가치를 구할 수 있습니다.

2) n 번째 물건을 가방에 넣을 수 없을 때 :

n 번째 물건을 가방에 넣을 수 없으므로 n - 1 번째 물건까지 진행한 데이터 주에서 넣은 물건의 무게 합이 K인 데이터의 가치 값이 n 번째 물건이 가방에 넣을 수 있는 최대 무게 K에 대하여 가방의 최대 가치가 되겠습니다.

 

Ex) 가방에 넣을 수 있는 물건의 최대 무게합(Bag_Max)이 7이고 다음과 같이 각 3개의 데이터를 주어질 때 

1. 사진기 : W = 4, V = 3

2. 노트북 : W = 5, V = 5

3. 핸드폰 : W = 3, V = 8

 

사진기 -> 노트북 -> 핸드폰 순으로 가방에 넣어본다고 생각해보겠습니다.

 

우선 사진기를 가방의 Bag_Max가 1 ~ 7일 때 가방의 최대 가치를 구합니다.

< 사진기 주어 질 때 >

가방의 Bag_Max가 1 ~ 3일 때 사진기를 넣을 수 없으므로 가방의 가치는 0입니다.

Bag_Max가 4 이상부터는 사진기를 넣을 수 있으므로 가방의 가치는 3이 됩니다.

이를 통하여 사진기만 주어질 때 가방의 Bag_Max에 따라 가방의 가치를 얻을 수 있습니다.

 

해당 데이터를 바탕으로 사진기 과 노트북이 주어졌을 때 가방의 Bag_Max가 1 ~ 7일 때 가방의 가치를 구하면 됩니다.

< 사진기 + 노트북 주어질 때 >

가방의 Bag_Max가 1 ~ 4일 때 노트북을 넣을 수 없으므로 가방의 가치는 사진기만 주어질 때의 Bag_Max 1 ~ 4과 같습니다.

가방의 Bag_Max가 5 이상부터는 노트북을 넣을 수 있으므로 다음과 같은 과정을 거쳐 가방의 가치를 측정합니다. 

사진기만 있을 때 Bag_Max - 노트북 W의 가방의 가치에 노트북에 V를 더한 값이 사진기만 있을 때 Bag_Max일 때의 가방의 가치를 비교하여 더 큰 값을 저장합니다.

 

ex) 6일 때 

< 노트북일 때 Bag_Max가 6일 때 >

사진기의 Bag_Max가 1일 때 가방의 가치(0)에 컴퓨터의 가치(5) 더한 값과 사진의 Bag_Max가 6일 때 가방의 가치(3)와 비교하여 더 큰 값인 5를 저장합니다.

 

마지막으로 핸드폰이 주어질 때 

< 사진기 + 노트북 + 핸드폰이 주어질 때 >

가방의 Bag_Max가 1, 2 일 때 핸드폰을 가방에 넣을 수 없으므로 사진기 + 노트북 주어질 때 가방의 Bag_Max가 1, 2일 때의 데이터를 가져옵니다. 3 이상부터는 핸드폰이 들어가므로 노트북과 마찬가지 방식을 통하여 가방의 가치를 구할 수 있습니다.

 

이렇게 표를 완성하였을 때 사진기, 노트북, 핸드폰이 주어지고 가방에 넣을 수 있는 물건의 최대 무게합이 7일 때 가방의 최고 가치는 11 임을 알 수 있습니다.

 

풀이 방법 : 

 

위에서 표를 통해 알 수 있듯이 2차원 배열을 사용하여 문제를 풀 수 있습니다. 또 다른 방법은 1차원 배열을 사용하는 것이 입니다.

데이터를 보면

사진기 + 데이터 X = 새로운 사진기 데이터 생성

노트북 + 사진기 데이터 = 새로운 사진기, 노트북 데이터 생성

핸드폰 + 사진기, 노트북 데이터 = 최종 데이터 생성

이 처럼 새로운 데이터를 생성함에 있어서 이전의 이전 데이터가 필요하지 않은 것을 확인할 수 있습니다. 즉, 일회성입니다. 따라서 1차원 배열을 사용하면 문제를 해결할 수 있습니다.

 

1) 2차원 배열 : DP[i][j] (i 범위 : 0 ~ N, j 범위 : 0 ~ K)을 선언합니다. 첫 번째 물건부터 i 번째까지의 물건을 살펴보고, 가방에 넣을 수 있는 최대 무게가 j이었을 때 가방에 들어간 물건의 가치 합의 최댓값 저장합니다. 따라서 i = 0, j = 0에서 시작하여 i = N, j = K를 수행하면 문제를 해결할 수 있습니다.

 

- K 값에 대하여 Bottom-up 방식

 

2) 1차원 배열 : DP[i] (i 범위 : 0 ~ K)을 선언합니다. 위와 마찬가지로 가방에 넣을 수 있는 최대 무게가 i일 때 가방에 들어간 물건의 가치 합의 최댓값을 저장합니다. 따라서 i = K, j = 0(물건 인덱스)에서 i = 0, j = N을 수행하면 문제를 해결할 수 있습니다.

 

- K 값에 대하여 Top-down 방식