백준(baekjoon) 12865번: 평범한 배낭(골드 5, 파이썬 PYTHON) - 동적 계획법 1

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

 

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

import sys

N,K=map(int,sys.stdin.readline().split())
bag=[]
dp=[[0 for _ in range(K+1)]for _ in range(N+1)]

for _ in range(N):
  W,V=map(int,sys.stdin.readline().split())
  bag.append([W,V])

for x in range(1,N+1):
  for y in range(K+1):
    if(bag[x-1][0]>y):
      dp[x][y]=dp[x-1][y]
    else:
      dp[x][y]=max(dp[x-1][y],bag[x-1][1]+dp[x-1][y-bag[x-1][0]])

print(dp[N][K])

 

※ 동적 계획법 1

 

 

● 먼저 N과 K에 각각 물품의 수와 버틸 수 있는 무게를 저장한다. 그리고 bag라는 빈 배열과 행의 크기가 N+1, 열의 크기가 K+1이고 초기값이 0인 2차원 배열 dp를 선언해준다(dp[x][y]에는 버틸 수 있는 무게가 y이고, 첫번째 부터 N번째 까지 물품 중 x번째 물품까지 고려했을 때 넣을 수 있는 물품들 가치의 최댓값이 저장된다).

 

● 그 후 입력되는 각 물품의 무게와 가치를 각각 W,V에 저장한 후 이를 배열에 넣어서 bag 배열에 차례대로 append 한다.

 

● x는 1부터 N까지, y는 0부터 K까지 돈다. x번째 물품의 무게와 가치는 bag[x-1]에 저장되어 있다. 각 단계에서 bag[x-1] 의 물품까지 고려하고 버틸 수 있는 무게는 y이다. 만약 bag[x-1][0] 즉, x번째 물품의 무게가 버틸 수 있는 무게 y보다 크다면 x번째 물품은 가방에 들어갈 수 없다. 따라서 dp[x][y]에 x-1번째 물품까지 고려하고 버틸 수 있는 무게는 똑같이 y일 때 넣을 수 있는 물품들 가치의 최댓값, 즉 dp[x-1][y]를 넣어준다.

 

● 만약 bag[x-1][0] 즉, x번째 물품의 무게가 버틸 수 있는 무게 y보다 작으면 x번째 물품을 가방에 넣거나 넣지 않거나 두가지의 선택지가 생긴다. 넣지 않을때의 가치의 최댓값은 x-1번째 물품까지 고려하고 버틸 수 있는 무게는 똑같이 y일 때 넣을 수 있는 물품들 가치의 최댓값이고, 넣을때 가치의 최댓값은 x번째 물품의 가치와 x-1번째 물품까지 고려하고 버틸 수 있는 무게는 y에서 이미 넣어준 x번째 물품의 무게를 뺀 무게일 때 넣을 수 있는 물품들 가치의 최댓값이다. 즉 dp[x][y]에 max(dp[x-1][y],bag[x-1][1]+dp[x-1][y-bag[x-1][0]]) 의 값을 넣어준다.

 

● 최종적으로 dp[N][K] 는 N번째 물품까지 고려하고 버틸 수 있는 무게가 K일 때의 넣을 수 있는 물품들 가치의 최댓값이 저장되어 있으므로 이를 출력해주면 답을 구할 수 있다.

 

 

결과