Notice
Recent Posts
Recent Comments
Link
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | |||
| 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| 19 | 20 | 21 | 22 | 23 | 24 | 25 |
| 26 | 27 | 28 | 29 | 30 | 31 |
Tags
- mysql
- data structure
- instruction
- control
- function
- github
- DB
- web
- DoM
- DS
- MIPS
- Class
- computer
- XML
- html
- Pipelining
- MacOS
- react
- python
- Java
- DATAPATH
- architecture
- Linux
- while
- CSS
- Algorithm
- javascript
- for
- php
- system
Archives
- Today
- Total
YYYEJI
[Algorithm] 배낭문제 DP로 풀기 본문
728x90
0-1 knapsac 문제는 제한된 가방 용량(W) 안에서 물건들의 가치(bi)와 무게(wi)가 주어졌을 때,
물건들을 조합해 최대의 가치를 가지도록 하는 문제입니다.
단, 각 물건은 딱 한 번만 사용할 수 있습니다.
배낭문제,수도코드(pseudo code)를 살펴보겠습니다.
for w = 0 to W
B[0, w] = 0
for i = 1 to n
B[i, 0] = 0
for w = 1 to W
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]해당 코드는 냅색(Napsack) 문제를 동적 계획법(Dynamic Programming)으로 푸는 방법 중 하나인 0/1 냅색 문제를 푸는 코드입니다.
위 코드에서 B[i, w]는 i번째 물건까지 고려하여 무게가 w일 때 최대로 취할 수 있는 가치를 나타내는데,
이 값을 이전에 구한 B[i-1, w] 값과 현재 물건의 무게(wi)와 가치 (bi)를 고려한 값(즉, bi+ B[i-1, w-wi] 중에서 더 큰 값을 구합니다.)
이렇게 하면 가방의 용향이 작아져도 가능한 물건들 중에서 최대 가치를 구할 수 있습니다.
0-1 knapsack problem
n = 4(# of elements)
W = 5(max weight)
Elements(weight, benefit value);
item 1: (2, 3)
item 2: (3, 4)
item 3: (4, 5)
item 4: (5, 6)
bottom
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | |||||
| 1 | |||||
| 2 | |||||
| 3 | |||||
| 4 | |||||
| 5 |
up
for w = 0 to W
B[0, w] = 0
코드를 보면 아래와 같이 표를 채울 수 있습니다.
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | ||||
| 1 | 0 | ||||
| 2 | 0 | ||||
| 3 | 0 | ||||
| 4 | 0 | ||||
| 5 | 0 |
for i = 1 to n
B[i, 0] = 0
코드도 아래와 같이 표를 채울 수 있습니다.
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | ||||
| 2 | 0 | ||||
| 3 | 0 | ||||
| 4 | 0 | ||||
| 5 | 0 |
표에 i, bi, wi, w, w-wi를 작성해줍니다.
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | i= 1, w= 1, bi= 3, wi= 2, w-wi = -1 |
i= 2, w= 1, bi= 4, wi= 3, w-wi = -2 |
i= 3, w= 1, bi= 5, wi= 4, w-wi = -3 |
i= 4, w= 1, bi= 6, wi= 5, w-wi = -4 |
| 2 | 0 | i= 1, w= 2, bi= 3, wi= 2, w-wi =0 |
i= 2, w= 2, bi= 4, wi= 3, w-wi = -1 |
i= 3, w= 2, bi= 5, wi= 4, w-wi = -2 |
i= 4, w= 2, bi= 6, wi= 5, w-wi = -3 |
| 3 | 0 | i= 1, w= 3, bi= 3, wi= 2, w-wi =1 |
i= 2, w= 3, bi= 4, wi= 3, w-wi = 0 |
i= 3, w= 3, bi= 5, wi= 4, w-wi = -1 |
i= 4, w= 3, bi= 6, wi= 5, w-wi = -2 |
| 4 | 0 | i= 1, w= 4, bi= 3, wi= 2, w-wi =2 |
i= 2, w= 4, bi= 4, wi= 3, w-wi = 1 |
i= 3, w= 4, bi=, 5 wi= 4, w-wi = 0 |
i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | i= 1, w= 5, bi= 3, wi= 2, w-wi =3 |
i= 2, w= 5, bi= 4, wi= 3, w-wi = 2 |
i= 3, w= 5, bi= 5, wi= 4, w-wi = 1 |
i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
i = 1, w = 1부터 살펴보겠습니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]wi <= w, 2<=1 이여서 false이기 때문데 else문으로 들어갑니다.
B[1, 1] = B[0, 1]이므로 0을 넣어줍니다.
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | i= 2, w= 1, bi= 4, wi= 3, w-wi = -2 |
i= 3, w= 1, bi= 5, wi= 4, w-wi = -3 |
i= 4, w= 1, bi= 6, wi= 5, w-wi = -4 |
| 2 | 0 | i= 1, w= 2, bi= 3, wi= 2, w-wi =0 |
i= 2, w= 2, bi= 4, wi= 3, w-wi = -1 |
i= 3, w= 2, bi= 5, wi= 4, w-wi = -2 |
i= 4, w= 2, bi= 6, wi= 5, w-wi = -3 |
| 3 | 0 | i= 1, w= 3, bi= 3, wi= 2, w-wi =1 |
i= 2, w= 3, bi= 4, wi= 3, w-wi = 0 |
i= 3, w= 3, bi= 5, wi= 4, w-wi = -1 |
i= 4, w= 3, bi= 6, wi= 5, w-wi = -2 |
| 4 | 0 | i= 1, w= 4, bi= 3, wi= 2, w-wi =2 |
i= 2, w= 4, bi= 4, wi= 3, w-wi = 1 |
i= 3, w= 4, bi=, 5 wi= 4, w-wi = 0 |
i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | i= 1, w= 5, bi= 3, wi= 2, w-wi =3 |
i= 2, w= 5, bi= 4, wi= 3, w-wi = 2 |
i= 3, w= 5, bi= 5, wi= 4, w-wi = 1 |
i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
다음으로 i = 1, w = 2로 넘어가겠습니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]wi<=w가 true이므로 이중 If문으로 들어가고 조건문을 판별합니다.
bi + B[i-1, w-wi] > B[i-1, w] = 3 + B[0, 0] >B[0, 2] = 3+0 > 0 이므로 true입니다.
B[1, 2] = 3+B[0, 0] = 3이므로 3이 값으로 들어갑니다.
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | i= 2, w= 1, bi= 4, wi= 3, w-wi = -2 |
i= 3, w= 1, bi= 5, wi= 4, w-wi = -3 |
i= 4, w= 1, bi= 6, wi= 5, w-wi = -4 |
| 2 | 0 | 3 | i= 2, w= 2, bi= 4, wi= 3, w-wi = -1 |
i= 3, w= 2, bi= 5, wi= 4, w-wi = -2 |
i= 4, w= 2, bi= 6, wi= 5, w-wi = -3 |
| 3 | 0 | i= 1, w= 3, bi= 3, wi= 2, w-wi =1 |
i= 2, w= 3, bi= 4, wi= 3, w-wi = 0 |
i= 3, w= 3, bi= 5, wi= 4, w-wi = -1 |
i= 4, w= 3, bi= 6, wi= 5, w-wi = -2 |
| 4 | 0 | i= 1, w= 4, bi= 3, wi= 2, w-wi =2 |
i= 2, w= 4, bi= 4, wi= 3, w-wi = 1 |
i= 3, w= 4, bi=, 5 wi= 4, w-wi = 0 |
i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | i= 1, w= 5, bi= 3, wi= 2, w-wi =3 |
i= 2, w= 5, bi= 4, wi= 3, w-wi = 2 |
i= 3, w= 5, bi= 5, wi= 4, w-wi = 1 |
i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
(1, 3)으로 넘어갑니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]wi <= w, 2<=3 참이므로 두 번째 조건을 판별합니다.
bi + B[i-1, w-wi] > B[i-1, w] = 3 + B[0, 1] > B[0, 3] = 3+0 > 0 이므로,
B[1, 3]에는 3+B[0, 1] = 3이 들어가게 됩니다.
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | i= 2, w= 1, bi= 4, wi= 3, w-wi = -2 |
i= 3, w= 1, bi= 5, wi= 4, w-wi = -3 |
i= 4, w= 1, bi= 6, wi= 5, w-wi = -4 |
| 2 | 0 | 3 | i= 2, w= 2, bi= 4, wi= 3, w-wi = -1 |
i= 3, w= 2, bi= 5, wi= 4, w-wi = -2 |
i= 4, w= 2, bi= 6, wi= 5, w-wi = -3 |
| 3 | 0 | 3 | i= 2, w= 3, bi= 4, wi= 3, w-wi = 0 |
i= 3, w= 3, bi= 5, wi= 4, w-wi = -1 |
i= 4, w= 3, bi= 6, wi= 5, w-wi = -2 |
| 4 | 0 | i= 1, w= 4, bi= 3, wi= 2, w-wi =2 |
i= 2, w= 4, bi= 4, wi= 3, w-wi = 1 |
i= 3, w= 4, bi=, 5 wi= 4, w-wi = 0 |
i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | i= 1, w= 5, bi= 3, wi= 2, w-wi =3 |
i= 2, w= 5, bi= 4, wi= 3, w-wi = 2 |
i= 3, w= 5, bi= 5, wi= 4, w-wi = 1 |
i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
(1, 4)로 넘어갑니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]첫 번째 조건을 만족하고,
두 번째 if문을 살펴보면 3 + B[0, 2] > B[0, 4] = 3+0>0 참이므로,
B[1, 4] = 3+B[0, 2] = 3이 value로 들어갑니다.
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | i= 2, w= 1, bi= 4, wi= 3, w-wi = -2 |
i= 3, w= 1, bi= 5, wi= 4, w-wi = -3 |
i= 4, w= 1, bi= 6, wi= 5, w-wi = -4 |
| 2 | 0 | 3 | i= 2, w= 2, bi= 4, wi= 3, w-wi = -1 |
i= 3, w= 2, bi= 5, wi= 4, w-wi = -2 |
i= 4, w= 2, bi= 6, wi= 5, w-wi = -3 |
| 3 | 0 | 3 | i= 2, w= 3, bi= 4, wi= 3, w-wi = 0 |
i= 3, w= 3, bi= 5, wi= 4, w-wi = -1 |
i= 4, w= 3, bi= 6, wi= 5, w-wi = -2 |
| 4 | 0 | 3 | i= 2, w= 4, bi= 4, wi= 3, w-wi = 1 |
i= 3, w= 4, bi=, 5 wi= 4, w-wi = 0 |
i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | i= 1, w= 5, bi= 3, wi= 2, w-wi =3 |
i= 2, w= 5, bi= 4, wi= 3, w-wi = 2 |
i= 3, w= 5, bi= 5, wi= 4, w-wi = 1 |
i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
(1, 5)로 넘어갑니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]첫 번째 조건을 만족하고,
두 번째 if문을 살펴보면 3 + B[0, 3] > B[0, 4] = 3+0>0 참이므로,
B[1, 5] = 3+B[0, 3] = 3이 value로 들어갑니다.
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | i= 2, w= 1, bi= 4, wi= 3, w-wi = -2 |
i= 3, w= 1, bi= 5, wi= 4, w-wi = -3 |
i= 4, w= 1, bi= 6, wi= 5, w-wi = -4 |
| 2 | 0 | 3 | i= 2, w= 2, bi= 4, wi= 3, w-wi = -1 |
i= 3, w= 2, bi= 5, wi= 4, w-wi = -2 |
i= 4, w= 2, bi= 6, wi= 5, w-wi = -3 |
| 3 | 0 | 3 | i= 2, w= 3, bi= 4, wi= 3, w-wi = 0 |
i= 3, w= 3, bi= 5, wi= 4, w-wi = -1 |
i= 4, w= 3, bi= 6, wi= 5, w-wi = -2 |
| 4 | 0 | 3 | i= 2, w= 4, bi= 4, wi= 3, w-wi = 1 |
i= 3, w= 4, bi=, 5 wi= 4, w-wi = 0 |
i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | 3 | i= 2, w= 5, bi= 4, wi= 3, w-wi = 2 |
i= 3, w= 5, bi= 5, wi= 4, w-wi = 1 |
i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
(2, 1)로 넘어갑니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]첫 번째 조건을 만족하지 않기 때문에 else 문으로 넘어가서 값을 넣어줍니다.
B[2, 1] = B[1, 1] = 0
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | i= 3, w= 1, bi= 5, wi= 4, w-wi = -3 |
i= 4, w= 1, bi= 6, wi= 5, w-wi = -4 |
| 2 | 0 | 3 | i= 2, w= 2, bi= 4, wi= 3, w-wi = -1 |
i= 3, w= 2, bi= 5, wi= 4, w-wi = -2 |
i= 4, w= 2, bi= 6, wi= 5, w-wi = -3 |
| 3 | 0 | 3 | i= 2, w= 3, bi= 4, wi= 3, w-wi = 0 |
i= 3, w= 3, bi= 5, wi= 4, w-wi = -1 |
i= 4, w= 3, bi= 6, wi= 5, w-wi = -2 |
| 4 | 0 | 3 | i= 2, w= 4, bi= 4, wi= 3, w-wi = 1 |
i= 3, w= 4, bi=, 5 wi= 4, w-wi = 0 |
i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | 3 | i= 2, w= 5, bi= 4, wi= 3, w-wi = 2 |
i= 3, w= 5, bi= 5, wi= 4, w-wi = 1 |
i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
(2, 2)로 넘어갑니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]첫 번째 조건을 만족하지 않기 때문에 else 문으로 넘어가서 값을 넣어줍니다.
B[2, 2] = B[1, 2] = 3
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | i= 3, w= 1, bi= 5, wi= 4, w-wi = -3 |
i= 4, w= 1, bi= 6, wi= 5, w-wi = -4 |
| 2 | 0 | 3 | 3 | i= 3, w= 2, bi= 5, wi= 4, w-wi = -2 |
i= 4, w= 2, bi= 6, wi= 5, w-wi = -3 |
| 3 | 0 | 3 | i= 2, w= 3, bi= 4, wi= 3, w-wi = 0 |
i= 3, w= 3, bi= 5, wi= 4, w-wi = -1 |
i= 4, w= 3, bi= 6, wi= 5, w-wi = -2 |
| 4 | 0 | 3 | i= 2, w= 4, bi= 4, wi= 3, w-wi = 1 |
i= 3, w= 4, bi=, 5 wi= 4, w-wi = 0 |
i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | 3 | i= 2, w= 5, bi= 4, wi= 3, w-wi = 2 |
i= 3, w= 5, bi= 5, wi= 4, w-wi = 1 |
i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
(2, 3)으로 넘어갑니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]첫 번째 조건을 만족하고,
두 번째 if문을 살펴보면 4 + B[1, 0] > B[1, 3] = 4+0>3 참이므로,
B[2, 3] = 4+B[1, 0] = 4이 value로 들어갑니다.
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | i= 3, w= 1, bi= 5, wi= 4, w-wi = -3 |
i= 4, w= 1, bi= 6, wi= 5, w-wi = -4 |
| 2 | 0 | 3 | 3 | i= 3, w= 2, bi= 5, wi= 4, w-wi = -2 |
i= 4, w= 2, bi= 6, wi= 5, w-wi = -3 |
| 3 | 0 | 3 | 4 | i= 3, w= 3, bi= 5, wi= 4, w-wi = -1 |
i= 4, w= 3, bi= 6, wi= 5, w-wi = -2 |
| 4 | 0 | 3 | i= 2, w= 4, bi= 4, wi= 3, w-wi = 1 |
i= 3, w= 4, bi=, 5 wi= 4, w-wi = 0 |
i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | 3 | i= 2, w= 5, bi= 4, wi= 3, w-wi = 2 |
i= 3, w= 5, bi= 5, wi= 4, w-wi = 1 |
i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
(2, 4)으로 넘어갑니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]첫 번째 조건을 만족하고,
두 번째 if문을 살펴보면 4 + B[1, 1] > B[1, 4] = 4+0>3 참이므로,
B[2, 4] = 4+B[1, 1] = 4이 value로 들어갑니다.
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | i= 3, w= 1, bi= 5, wi= 4, w-wi = -3 |
i= 4, w= 1, bi= 6, wi= 5, w-wi = -4 |
| 2 | 0 | 3 | 3 | i= 3, w= 2, bi= 5, wi= 4, w-wi = -2 |
i= 4, w= 2, bi= 6, wi= 5, w-wi = -3 |
| 3 | 0 | 3 | 4 | i= 3, w= 3, bi= 5, wi= 4, w-wi = -1 |
i= 4, w= 3, bi= 6, wi= 5, w-wi = -2 |
| 4 | 0 | 3 | 4 | i= 3, w= 4, bi=, 5 wi= 4, w-wi = 0 |
i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | 3 | i= 2, w= 5, bi= 4, wi= 3, w-wi = 2 |
i= 3, w= 5, bi= 5, wi= 4, w-wi = 1 |
i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
(2, 5)로 넘어갑니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]첫 번째 조건을 만족하고,
두 번째 if문을 살펴보면 4 + B[1, 2] > B[1, 5] = 4+3 > 3 참이므로,
B[2, 5] = 4+B[1, 2] = 4+3 = 7이 value로 들어갑니다.
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | i= 3, w= 1, bi= 5, wi= 4, w-wi = -3 |
i= 4, w= 1, bi= 6, wi= 5, w-wi = -4 |
| 2 | 0 | 3 | 3 | i= 3, w= 2, bi= 5, wi= 4, w-wi = -2 |
i= 4, w= 2, bi= 6, wi= 5, w-wi = -3 |
| 3 | 0 | 3 | 4 | i= 3, w= 3, bi= 5, wi= 4, w-wi = -1 |
i= 4, w= 3, bi= 6, wi= 5, w-wi = -2 |
| 4 | 0 | 3 | 4 | i= 3, w= 4, bi=, 5 wi= 4, w-wi = 0 |
i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | 3 | 7 | i= 3, w= 5, bi= 5, wi= 4, w-wi = 1 |
i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
(3, 1)로 넘어갑니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]첫 번째 조건을 만족하지 않기 때문에 else 문으로 넘어가서 값을 넣어줍니다.
B[3, 1] = B[2, 1] = 0
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | i= 4, w= 1, bi= 6, wi= 5, w-wi = -4 |
| 2 | 0 | 3 | 3 | i= 3, w= 2, bi= 5, wi= 4, w-wi = -2 |
i= 4, w= 2, bi= 6, wi= 5, w-wi = -3 |
| 3 | 0 | 3 | 4 | i= 3, w= 3, bi= 5, wi= 4, w-wi = -1 |
i= 4, w= 3, bi= 6, wi= 5, w-wi = -2 |
| 4 | 0 | 3 | 4 | i= 3, w= 4, bi=, 5 wi= 4, w-wi = 0 |
i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | 3 | 7 | i= 3, w= 5, bi= 5, wi= 4, w-wi = 1 |
i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
(3, 2)로 넘어갑니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]첫 번째 조건을 만족하지 않기 때문에 else 문으로 넘어가서 값을 넣어줍니다.
B[3, 2] = B[2, 2] = 3
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | i= 4, w= 1, bi= 6, wi= 5, w-wi = -4 |
| 2 | 0 | 3 | 3 | 3 | i= 4, w= 2, bi= 6, wi= 5, w-wi = -3 |
| 3 | 0 | 3 | 4 | i= 3, w= 3, bi= 5, wi= 4, w-wi = -1 |
i= 4, w= 3, bi= 6, wi= 5, w-wi = -2 |
| 4 | 0 | 3 | 4 | i= 3, w= 4, bi=, 5 wi= 4, w-wi = 0 |
i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | 3 | 7 | i= 3, w= 5, bi= 5, wi= 4, w-wi = 1 |
i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
(3, 3)으로 넘어갑니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]첫 번째 조건을 만족하지 않기 때문에 else 문으로 넘어가서 값을 넣어줍니다.
B[3, 3] = B[2, 3] = 4
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | i= 4, w= 1, bi= 6, wi= 5, w-wi = -4 |
| 2 | 0 | 3 | 3 | 3 | i= 4, w= 2, bi= 6, wi= 5, w-wi = -3 |
| 3 | 0 | 3 | 4 | 4 | i= 4, w= 3, bi= 6, wi= 5, w-wi = -2 |
| 4 | 0 | 3 | 4 | i= 3, w= 4, bi=, 5 wi= 4, w-wi = 0 |
i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | 3 | 7 | i= 3, w= 5, bi= 5, wi= 4, w-wi = 1 |
i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
(3, 4)로 넘어갑니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]첫 번째 조건을 만족하고,
두 번째 if문을 살펴보면 5 + B[2, 0] > B[2, 4] = 5+0 > 4 참이므로,
B[3, 4] = 5+B[2, 0] = 5+0 = 5가 value로 들어갑니다.
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | i= 4, w= 1, bi= 6, wi= 5, w-wi = -4 |
| 2 | 0 | 3 | 3 | 3 | i= 4, w= 2, bi= 6, wi= 5, w-wi = -3 |
| 3 | 0 | 3 | 4 | 4 | i= 4, w= 3, bi= 6, wi= 5, w-wi = -2 |
| 4 | 0 | 3 | 4 | 5 | i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | 3 | 7 | i= 3, w= 5, bi= 5, wi= 4, w-wi = 1 |
i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
(3, 5)로 넘어갑니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]첫 번째 조건을 만족하고,
두 번째 if문을 살펴보면 5 + B[2, 1] > B[2, 5] = 5+0 > 7 거짓이므로 else로 넘어갑니다.
B[3, 5] = B[2, 5] = 7이 value로 들어갑니다.
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | i= 4, w= 1, bi= 6, wi= 5, w-wi = -4 |
| 2 | 0 | 3 | 3 | 3 | i= 4, w= 2, bi= 6, wi= 5, w-wi = -3 |
| 3 | 0 | 3 | 4 | 4 | i= 4, w= 3, bi= 6, wi= 5, w-wi = -2 |
| 4 | 0 | 3 | 4 | 5 | i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | 3 | 7 | 7 | i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
(4, 1)로 넘어갑니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]첫 번째 조건을 만족하지 않기 때문에 else 문으로 넘어가서 값을 넣어줍니다.
B[4, 1] = B[3, 1] = 0
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 3 | 3 | 3 | i= 4, w= 2, bi= 6, wi= 5, w-wi = -3 |
| 3 | 0 | 3 | 4 | 4 | i= 4, w= 3, bi= 6, wi= 5, w-wi = -2 |
| 4 | 0 | 3 | 4 | 5 | i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | 3 | 7 | 7 | i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
(4, 2)로 넘어갑니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]첫 번째 조건을 만족하지 않기 때문에 else 문으로 넘어가서 값을 넣어줍니다.
B[4, 2] = B[3, 2] = 3
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 3 | 3 | 3 | 3 |
| 3 | 0 | 3 | 4 | 4 | i= 4, w= 3, bi= 6, wi= 5, w-wi = -2 |
| 4 | 0 | 3 | 4 | 5 | i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | 3 | 7 | 7 | i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
(4, 3)으로 넘어갑니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]첫 번째 조건을 만족하지 않기 때문에 else 문으로 넘어가서 값을 넣어줍니다.
B[4, 3] = B[3, 3] = 4
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 3 | 3 | 3 | 3 |
| 3 | 0 | 3 | 4 | 4 | 4 |
| 4 | 0 | 3 | 4 | 5 | i= 4, w= 4, bi= 6, wi= 5, w-wi = -1 |
| 5 | 0 | 3 | 7 | 7 | i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
(4, 4)로 넘어갑니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]첫 번째 조건을 만족하지 않기 때문에 else 문으로 넘어가서 값을 넣어줍니다.
B[4, 4] = B[3, 4] = 5
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 3 | 3 | 3 | 3 |
| 3 | 0 | 3 | 4 | 4 | 4 |
| 4 | 0 | 3 | 4 | 5 | 5 |
| 5 | 0 | 3 | 7 | 7 | i= 4, w= 5, bi= 6, wi= 5, w-wi = 0 |
(4, 5)로 넘어갑니다.
if wi <= w
if bi + B[i-1, w-wi] > B[i-1, w]
B[i,w] = bi + B[i-1, w-wi]
else B[i,w] = B[i-1, w]
else B[i, w] = B[i-1, w]첫 번째 조건을 만족하고,
두 번째 if문을 살펴보면 6 + B[3, 0] > B[3, 5] = 6+0 > 7 거짓이므로 else로 넘어갑니다.
B[4, 5] = B[3, 5] = 7이 value로 들어갑니다.
| w \ i | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 3 | 3 | 3 | 3 |
| 3 | 0 | 3 | 4 | 4 | 4 |
| 4 | 0 | 3 | 4 | 5 | 5 |
| 5 | 0 | 3 | 7 | 7 | 7 |
이렇게 최적의 해는 7이 됩니다.
◡̈
'Algorithm' 카테고리의 다른 글
| [Algorithm] 배낭문제, 냅색(Knapsack)이란? (0) | 2023.04.18 |
|---|---|
| [Algorithm] Greedy로 Huffman code 풀기 (0) | 2023.04.18 |
| [Algorithm] DP로 MCM(Matrix-Chain Multiplication) 풀기 (0) | 2023.04.16 |
| [Algorithm] 마스터 정리 (Master Theorem) (0) | 2023.04.16 |
| [Algorithm] 재귀 트리(Recursion Tree Theorem) (0) | 2023.04.16 |
'Algorithm' Related Articles
more
