Algorithm

[Algorithm] 배낭문제 DP로 풀기

YEJI ⍢ 2023. 4. 19. 00:01
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이 됩니다.

 

 

◡̈