0/1 배낭 문제(Knapsack Problem) - 파이썬(DP)

사이트 링크 : https://codeup.kr/problem.php?id=3740&rid=0

 

문제는 아래와 같습니다.

문제

어떤 배낭에 W무게 만큼 물건을 담을 수 있다.

물건들은 (무게 Wi, 가격 Vi) 정보를 가지고 있는데, 물건들을 조합해서 담아 가격의 총합이 최대가 되게 하려고 한다.

물건들은 한 종류씩 밖에 없으며, 절대 배낭의 무게를 초과해서는 안 된다.

 

입력

• 첫째 줄에 물건의 개수 N(1<= N <= 100)과 배낭의 무게 W( 1 <= W <= 10000 )가 입력된다.
• 둘째 줄부터 N+1째줄 까지 물건들의 정보가 wi, vi가 한 줄에 하나씩 입력된다. ( 1 <= Wi, Vi <= 100 )

출력

• 배낭의 무게 W를 초과하지 않으면서 물건의 가격의 총합의 최대값을 출력한다.

문제 해결 포인트 

• 배낭 문제 가 이렇게 유명한지 모르고 쉽게 생각하고 풀다가 시간을 엄청 소요한 문제입니다. 
• 결국 문제의 아이디어를 보고 풀기는 했지만 아이디어를 이해하는것 까지 시간이 오래 걸렸습니다. 
• 문제 아이디어를 정리하면 아래와 같습니다. 

링크의 문제에 예제 값을 표로 만들어서 정리를 해보았습니다. 

0/1 Kanpsack Problem DP 해결 과정

가방에 담을수 있는 물건 무게와 가격을 정리하였습니다. 

물건	1	2	3	4
무게(w)	2	1	3	2
가격(v)	3	2	3	2

 

2차원 배열을 생성하고 각 행과열에 i 번째 물건까지 넣을수 있고 배낭에 넣을수 있는 무게가 j 라고 하였을때 물건들의 가격 최대치를 빈칸안에 넣도록 하겠습니다. 

 

우선 이차원 배열생성후 열값 (j)은 물건이 들어갈 최대 크기 행 값은 i번째 물건으로 각 행과 열의값을 구성합니다. 

(물론 이차월 배열에 0의 i,j 값을 빠져도 상관이 없지만 저는 0을 추가해서 1부터 시작하도록 하였습니다.)

	0	1	2	3	4	5
0
1
2
3
4

 

 

첫번째 물건을 넣었을때 (무게: 2,가격 3) 을 넣었을떼 가방의 최대이윤은 아래 표와 같습니다. 

 

	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	0	3	3	3	3
2
3
4

 

첫번째 물건을 넣었을때 (무게: 2,가격 3) 을 넣었을떼 가방의 최대이윤은 아래 표와 같습니다.

 

	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	0	3	3	3	3
2
3
4

 

두번째 물건을 넣었을때 (무게: 1,가격 2) 을 넣었을떼 가방의 최대이윤은 아래 표와 같습니다.

 

	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	0	3	3	3	3
2	0	2	3	5	5	5
3
4

 

세번째 물건을 넣었을때 (무게: 3,가격 3) 을 넣었을떼 가방의 최대이윤은 아래 표와 같습니다.

 

	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	0	3	3	3	3
2	0	2	3	5	5	5
3	0	2	3	5	5	6
4

 

네번째 물건을 넣었을때 (무게: 2,가격 2) 을 넣었을떼 가방의 최대이윤은 아래 표와 같습니다.

 

	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	0	3	3	3	3
2	0	2	3	5	5	5
3	0	2	3	5	5	6
4	0	2	3	5	5	7

 

 

표를 보시면 최대이윤은 

 

각 물건의 가치 v[i]

각 물건의 무게 w[i]

dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]) (단 w[i] <= j 조건)

 

해당 문제는 dn(입력받은 물건 무게 리스트) 과 dw(입력받은 물건 가격 리스트)로 표기를 했습니다. 

 

정답코드

 

복붙 가능코드

n, w = map(int, input().split())
dn = [0]
dw = [0]
for _ in range(n):
    x, y = map(int, input().split())
    dn.append(x)
    dw.append(y)

dp = [[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, w+1):
        if dn[i] <= j:
            dp[i][j] = max(dp[i-1][j], dw[i] + dp[i-1][j-dn[i]])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[n][w])

해당 문제는 계속 리뷰를 해서 코드를 정교화 해보는것도 좋은것 같습니다.