[BOJ] 23061 백남이와 여행 준비

 

[출처: 백준 온라인 저지]

문제

방학을 맞은 귀여운 백남이는 여행을 떠날 준비를 하고 있다.

백남이는 여행에 필요하다고 생각하는 필수품 N$N$개를 가지고 있다. 각 물건은 무게 W$W$와 가치 V$V$를 가진다. 그리고 백남이는 물건을 담을 가방 M$M$개를 가지고 있는데, 각각의 가방은 최대 Ki$K_i$만큼의 무게를 견딜 수 있다.

MBTI가 J(판단형)인 백남이는 효율성을 중요하게 여기기 때문에, 가장 효율적으로 짐을 싸지 않으면 여행을 출발할 수 없다. 백남이가 정의한 효율성은 (가방에 담긴 물건의 가치의 합) / (가방이 견딜 수 있는 최대 무게)이다.

가방과 물건의 정보가 주어졌을 때, 가장 효율적으로 짐을 싸기 위해 필요한 가방이 무엇인지 알아내자. 가방은 한 개만 선택할 수 있으며, 최적의 가방이 여러 가지라면 그중 가장 작은 번호를 출력한다.

 

입력

첫 줄에 물품의 수 N(1≤N≤100)$N(1 ≤ N ≤ 100)$과 가방의 수 M(1≤M≤100)$M(1 ≤ M ≤ 100)$가 주어진다.

두 번째 줄부터 N$N$ 개의 줄에 거쳐 각 물건의 무게 W(1≤W≤100,000)$W(1 ≤ W ≤ 100,000)$와 해당 물건의 가치 V(0≤V≤1,000)$V(0 ≤ V ≤ 1,000)$가 주어진다.

그 후에는 M$M$ 개의 줄에 거쳐 가방이 버틸 수 있는 최대 무게 Ki(1≤Ki≤1,000,000)$K_i (1 ≤ K_i ≤ 1,000,000)$가 주어진다. 가방의 번호는 1$1$부터 M$M$까지이다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 가장 효율적으로 짐을 싸기 위해 필요한 가방의 번호를 출력한다.

풀이

랜덤으로 문제를 돌리던 와중 이 문제가 나왔고, 평소에 배낭 문제에 대해 듣기만 했지 풀어본 적이 없었기에 풀기로 작심하였다. 인터넷에 배낭문제 알고리즘을 검색한 후, 크게 두 가지 종류가 있다는 것을 알았다. 이 부분은 테리의 일상 블로그를 참조하였다(https://dheldh77.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9CKnapsack-Problem). 물건을 쪼갤 수 있는 배낭 문제는 가치가 큰 물건부터 담고, 남은 무게만큼 물건을 쪼개는 방식으로 그리디 알고리즘으로 해결할 수 있다고 한다. 일단 제일 무거운 것부터 넣는 방법으로 비교적 쉬운 유형인 것 같다. 두 번째는 문제를 쪼갤 수 없는 경우인데 이 때는 동적 계획법을 사용해야 한다고 한다. 내가 이해한 것이 맞다면? 먼저 2차원 dp배열을 선언한 후에 열은 최대 무게, 행은 물건의 갯수로 선언해준다. 위 문제 같은 경우에는 열이 1000000개이지만, 조금이라도 시간 효율성을 높이려고 주어진 가방 중에 가장 무거운 무게를 열의 최대 크기로 설정하였다. 그 다음 물건의 갯수 n을 행, 즉 i로 설정하였다. 그 다음 i, j에 대하여 탐색을 돌면서 만약 최대 무게(j)보다 물건의 무게가 적으면 그 물건의 가치가 가방에 담긴 것이기 때문에 dp 배열 안에 넣어준다. 이런 식으로 가다보면 만약 가방이 견딜 수 있는 무게가 15이고, 남은 무게가 4일 때, 앞에서 구한 무게가 4일 때 들 수 있는 최대 무게를 가져와서 쓸 수 있기 때문에 동적 계획법을 사용하는 것이다. 이런 식으로 dp 배열을 전부 구했으면, 효율성을 따져야 하는데 이 때 소수점으로 비교를 할 경우 오차가 발생할 수 있다. 그러므로 각자의 무게로 나누는 것이 아닌, 비교하는 두 배냥 각자의 무게를 서로의 무게를 곱해준 다음 비교하였다.

import sys
input = lambda: sys.stdin.readline().rstrip()
n, m = map(int, input().split())
item = [[0, 0]]
for _ in range(n):
  item.append(list(map(int, input().split())))
max_effi = 0
bag = [0]
for _ in range(m):
  bag.append(int(input()))
maxBag = max(bag)
dp = [[0 for _ in range(maxBag+1)]for _ in range(n+1)]
for i in range(1, n+1):
  for j in range(1, maxBag+1):
    if item[i][0] <= j:
      dp[i][j] = max(item[i][1] + dp[i-1][j-item[i][0]], dp[i-1][j])
    else:
      dp[i][j] = dp[i-1][j]
ans = 1
for i in range(2, m+1):
  val1 = dp[n][bag[ans]] * bag[i]
  val2 = dp[n][bag[i]] * bag[ans]
  if val2 > val1: ans = i
print(ans)