https://www.acmicpc.net/problem/12865
성능 요약
메모리: 115112 KB, 시간: 156 ms
분류
다이나믹 프로그래밍, 배낭 문제
문제 설명
이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 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)가 주어진다.
입력으로 주어지는 모든 수는 정수이다.
출력
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.
아이디어, 문제풀이
- 앞서 풀이했던 백준 동전문제와 동일한 풀이를 적용하면 풀어낼 수 있다.
- dp는 버틸수 있는 무게로 정의한다.
- 그 무게에 도달한 총 가치합중 가장 큰것을 저장한다.
TROUBLE SHOOTING
-
내가 내 뇌로 풀 수 있었던 마지막 dp 문제.
-
이 문제가 어려웠던건,
#k 부터 1 까지 역순으로 for문을 돌린다 / 독립성을 보장하기 위해서
for i in range(k, 0, -1):
if i < weight:
continue
if i >= weight:
dp[i] = max(dp[i], dp[i-weight]+value)결론적으론 이 코드가 문제였다. 우리에게 익숙하지 않은게 보이는데 for문을 역순으로 돌린다는 점이다. 아직도 이해못헀다 사실… 이게 정말 기분 나쁜게, 정순으로 for문을 사용하더라도, 대부분의 예제들은 모두 통과를 하는데, 백준에 제출하면 틀렸다고 나온다. 이유는 독립성을 보장하지 못하기 때문.
이 독립성을 쉽게 이해하지 못해서, 처음엔 다른 방법으로 구현해 보려고 했다. 반례의 조건을 찾아 그 반례들을 제외해주거나, for문안의 if 문을 다듬거나… 하는 방법으로 구현했는데, 결국 실패 했다. 역순으로 풀이를 했을때 머릿속으로는 그려져서 이해했지만, 아직 확실한 설명을 이 글에 작성하지 못할것 같다.
보통은 이 문제를 2차원 dp배열을 통해 풀이를 하는걸로 봐선, 초반에 잘못된 접근을 한게 아닐까 싶다. 2차원 배열로 다시 풀어내거나, 역순에 대한 설명이 가능해 지게 되면 다시 이 글을 수정하러 오겠다. (그래도 내 알고리즘 깔끔하게 문제를 해결했다!)
코드
#https://www.acmicpc.net/problem/12865
#평범한 배낭
#12865
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
graph = []
for _ in range(n):
w, v = map(int, input().split())
graph.append([w,v])
# print(graph)
dp = [0] * (k+1)
# n = 물품의 수 / k = 버틸수 있는 무게 / graph = (무게, 가치)
def fun(k, graph):
for node in graph:
weight = node[0]
value = node[1]
#k 부터 1 까지 역순으로 for문을 돌린다 / 독립성을 보장하기 위해서
for i in range(k, 0, -1):
if i < weight:
continue
if i >= weight:
dp[i] = max(dp[i], dp[i-weight]+value)
return dp
result = fun(k, graph)
# print(result)
answer = result[k]
print(answer)