[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파
START :
[3코1파] 2023.01.04~ (292일차)
[4코1파] 2023.01.13~ (284일차)
[4코3파] 2023.10.01 ~ (22일차)
Today :
2023.10.22 [292일차]
Knapsack Problem(배낭 문제)
문제 설명
물건 n개의 집합 S={1,2,...,n} 와 W={w1,w2,...,wn}, P={p1,p2,...,pn}가 주어져 있다.
배낭에 이러한 물건들을 넣어 시장에 판다고 할 때, 얻을 수 있는 최대 이윤을 구한다.
0-1 배낭 문제
어떤 배낭이 있고 그 배낭안에 넣을 수 있는 최대 무게는 K.
배낭에 넣을 수 있는 N개의 물건은 각기 다른 무게 W와 가치 V를 가지고 있음.
배낭이 담을 수 있는 최대한 가치의 물건의 조합을 찾는 문제
유사 문제: 백준 12865번
https://www.acmicpc.net/problem/12865
문제 풀이 방법
해당 문제가 Dynamic Programming의 대표 문제인데,
물건을 쪼갤 수 있으면 Fractional Knapsack이고, 쪼갤 수 없는 경우에는 0-1 배낭문제라고 불린다고 한다.
Fractional Knapsack은 greedy algorithmn 으로 풀고,
0-1 배낭 문제는 Dynamic Programming 으로 푼다고 한다.
일단 위에서 언급한 문제(백준 12865)는 0-1 배낭문제이다.
다들 표를 채우는 식을 나열해놨는데 도통 이해가 안갔었다.
그러다가 배낭문제를 쉽게 a-z까지 떠먹여주는 블로그를 보고 이해해봤다.
일단, 해당 문제가 최대 이익을 구하는 문제이긴 하지만 주어진 가방에 물건을 넣는다/넣지 않는다라는 두 선택지를 반복하고 있다는 본질을 이해해야 한다는 것이다.
최대 K를 담을 수 있는 배낭에 무게 W와 가치가 V인 물건을 담는다면,
현재 가치는 V, 배낭에는 최대 (K-W)를 더 넣을 수 있게 된다.
이 말은 무게 W를 제외하고 최대 (K-W)를 담을 수 있는 배낭이라는 소리고, 이때의 최대 가치는 V다 라는 문제로 치환이 가능하게 된다.
해당 물건들을 탐색할 때의 인덱스를 i 라고 하고 최대 무게를 k라고 한다면
최대이익은 [i][k]로 나타낼 수 있는데, 최대 무게가 k인 배낭에서 i 번째 물건까지 판단했을 때의 최대 가치라는 소리이다.
예를 들어 W = [3, 1, 6, 5, 2, 3], V = [4, 2, 5, 6, 1, 3] 에서 각 W,V의 인덱스는 해당하는 무게와 가치를 나타내고 최대 6kg 가방이라고 한다면
네 번째 가방까지 확인 했을 때는 최대이익[4][6]은, 최대 무게의 6kg에서 4번째 물건까지 진행 했을 때의 최대 이익이다. (i=4, k=6)
이를 이용해 점화실을 만들어 본다면,
최대 이익을 dp[i][k] 라고 한다면, 최대 k까지 담을 수 있는 배낭을 i번째 물건까지 봤다는 뜻이다.
이 때 i(현재 까지 본 물건) 후에 다음 물건인 i+1번째를 넣을까 말까 고민해보자.
이 때는 경우의 수가 두 개 존재한다.
(1) 물건의 무게가 배낭 무게를 초과해버릴때
이때는 물건을 넣지 못하기 때문에 무게에 변화도 없고, 최대의 가치는 dp[i][k] 를 유지한다.
이때의 점화식은 dp[i+1][k] = dp[i][k] 이다.
(2) 물건의 무게가 배낭 무게를 초과하지 않을
이때 또한 물건을 넣느냐, 넣지않느냐의 두 가지 경우의 존재한다.
물건을 넣지 않는다면 dp[i+1][k] = dp[i][k] 를 유지한다.
물건을 넣는다면 dp[i+1][k] = i+1가치 + dp[i][k-w] 로 치환이 가능하다.
최대 k 무게에서 i+1을 담는다면,
배낭은 최대 k에서 i+1의 물건의 무게(wk라고 가정)를 뺀 k-wk 가되는 것이고,
현재의 가치는 i까지의 최대 가치를 가지고 있는 것이라는 것이다.
현재 i 번째 물건을 넣기 위해 넣었던 물건을 뺐을 때의 가치와 현재 물건의 가치를 더해주는 것이다.
즉, 물건의 무게가 배낭의 무게를 초과하지 않을 경우에는
물건을 넣지 않았을때의 이전의 가치와, 물건을 넣고난 뒤의 가치 두 중 큰 값을 선택하면 된다.
이를 정리하면
케이스 1. 물건 w의 무게 > 배당 k의 무게
dp[i][k] = dp[i-1][k]
케이스 2. 물건 w의 무게 <= 배낭 k의 무게
dp[i][k] = max(dp[i-1][k], i번째 가치 + dp[i-1][k-i번째무게])
라는 점화식으로 바꿀 수 있다.
각 물건의 무게에 따라서 넣을 수 있는 최대의 가치를 찾는 subproblem으로 변환해서 푸는 DP 문제이다.
이렇게 최대 가치를 확인하는 과정을 brute force로 한다면 n 개의 조합을 만들기 위해서는 O(2^n)가 걸리게 된다.
이지만 DP로 푼다면 2차원 배열을 채워주면 되기 때문에 물건의 무게와 갯수에 다른 O(N*K)가 걸리게 된다.
내 코드
백준으로 다시 풀어봄
이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.
입력
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.
입력으로 주어지는 모든 수는 정수이다.
출력
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.
2D array
import sys
N, K = map(int, input().split())
items = [[0,0]]
bag = [[0]*(K+1) for _ in range(N+1)]
for _ in range(N):
items.append(list(map(int, input().split())))
for i in range(1,N+1):
for j in range(1, K+1):
w, v = items[i][0], items[i][1]
if w>j:
bag[i][j] = bag[i-1][j]
else:
bag[i][j] = max(bag[i-1][j], v+bag[i-1][j-w])
bag[N][K]1D array
import sys
N,K = map(int,input().split())
items = []
for _ in range(N):
w,v = map(int,input().split())
items.append((w,v))
dp = [0 for _ in range(K+1)]
for item in items:
w,v = item
for i in range(K,w-1,-1):
dp[i] = max(dp[i],dp[i-w]+v)
print(dp[-1])
증빙
여담
Leetcode에 있는 Dynamic Programming 문제를 10문제 넘게 풀었음에도 불구하고 마지막까지 감을 못잡는 것 같아서, 어제 풀었던 leetcode 416. Partition Equal Subset Sum 문제가 배낭 문제와 유사하다고 해서 찾아봤다.
배낭 문제가 DP에서 유명한 문제인데, 이 문제 풀이법을 그나마 사람들이 이해하기 쉽게 풀어놓은게 많아서 기초 중의 상기초로 다시 돌아왔음
그나저나 프로그래머스랑 릿코드하다가 백준하려니까 map, int 런타임 때문에 2번 탈락~
추후에 N,K 1 부터 넣어주는 코드로 하다가 최적화 코드를 발견했다.
dp는 저렇게 예쁘게 짜줘야지..
이해할 수 있게 도와줬던 개발 블로그
https://howudong.tistory.com/106
그 와중에 백준하면서 알게된 사실은 주피터 노트북에서는 sys의 stdin이 제대로 구성되어 있지 않아서,
백준에서 테스트 하듯 sys.stdin.readline 으로 하면 입력 받지 못하고 빈 값으로 반환된다고 함
