<문제 링크>
https://www.acmicpc.net/problem/12865
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
<풀이>
이 문제는 동적 프로그래밍 이용해 중복된 연산을 줄여 시간을 단축해야하는 문제이다.
N, K까지의 최적값들을 계산해 최종 N, K일 때 최고의 가치가 몇 일지를 구해야 한다.
따라서 DP의 크기는 [N+1][K+1]이다. ([넣을 수 있는 물품 수][배낭 최대 무게 한도])
배낭 문제 알고리즘에 대한 DP 연산식은 다음과 같다. (v=objects[][1], w=objects[][0])
if 조건문에 해당하는 부분을 먼저 해석하자면,
(i에 해당하는 물건의 무게(w, 기존에 계산하지 않은 새로운 물건?)가 현재 포커싱중인 배낭 무게 한도(W)보다 작을 경우),
MAX(w가 들어갈 수 있는 배낭 무게, w가 들어가지 않았을 때 최적값)을 비교해 return되는 값(둘 중 큰 값)을 dp[i][j]에 넣어줍니다.
그렇다면 반대로 (w가 W보다 클 경우),
현재 배낭에는 w를 못 넣기 때문에 dp[i-1][j](기존 최적값)를 dp[i][j]에 넣어줍니다.
이런 식으로 dp를 완성하고 내가 원하는 dp[N][K]를 리턴해 출력해주면 끝
<코드>
N, K: 넣을 수 있는 물품 수, 배낭 무게 한도
objects[0]: 물건 무게
objects[1]: 물건의 가치
dp: 동적 프로그래밍 결과
def DP(N, K, objects):
dp = [[0 for j in range(K+1)] for i in range (N+1)] # init
# logic
for i in range(1, N+1):
for j in range(1, K+1):
if objects[i-1][0] <= j: # 0부터 시작하기 때문에 i-1, 무게 한도를 넘지 않고 넣을 물건이 있다면
# 새로운 물건을 넣었을 때와 기존 최적값을 비교해 큰 값을 선택
dp[i][j] = max(objects[i-1][1] + dp[i-1][j - objects[i-1][0]], dp[i-1][j])
else: # 새로운 물건을 넣을 수 없기 때문에 기존 최적값 선택
dp[i][j] = dp[i-1][j]
return dp[N][K]
if __name__ == "__main__":
N, K = map(int, input().split()) # 물품 수, 무게 한도
objects = []
# input
for i in range(N):
objects.append([])
W, V = map(int, input().split())
objects[i].append(W)
objects[i].append(V)
print(DP(N, K, sorted(objects, key=lambda x : x[0])))
'~2023' 카테고리의 다른 글
| [Python] 백준 7662번 문제, 이중 우선순위 큐 (0) | 2021.07.12 |
|---|---|
| [Python] 백준 2156번 문제, 포도주 시식 (0) | 2021.07.12 |
| [Python] 백준 2178번 문제, 미로 탐색 (0) | 2021.07.04 |
| [JAVA] 백준 17478번 문제, 재귀함수가 뭔가요? (0) | 2021.07.04 |
| [JAVA/PYTHON] 백준 1158번 문제, 요세푸스 문제 (0) | 2021.06.26 |