백준 : 평범한 배낭(12865) with 파이썬

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

12865번: 평범한 배낭

문제

이문제는 첫 줄에서 물품의 수 N, 버틸 수 있는 무게 K를 입력받은 뒤 물품의 무게 W를 고려하여 물건의 가치 V의 최댓값을 구하는 문제이다. 

 

문제풀이

이문제를 이해하기위해 예제의 입력값과 출력값을 표를 통해 직관적으로 분석해보려한다.

 

물품의 수 N = 4

버틸 수 있는 무게 K = 7

물건의 무게 W = 6, 4, 3, 5

물건의 가치 V = 13, 8, 6, 12

위 문제의 입출력값을 표로 작성하였다.

표를 보면 행은 버틸 수 있는 무게 = K,

                열은 물품의 무게 / 물품의 가치 = W / V 이다.

위 표에서 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 조합하기 위해서 과정은 아래와 같다

이를 점화식으로 세워 보면 

dp[i][j] = max(dp[i - 1][j], V + dp[i - 1][j - W]) 

 

작성한 코드를 상세히 분석해보려한다.

import sys

input = sys.stdin.readline

N, K = map(int, input().split())

add = [[0,0]]

dp = [[0] * (10001) for _ in range(101)]

for i in range(1, N + 1):

W, V = map(int, input().split())

add.append([W, V])

 

for i in range(1, N + 1):

     for j in range(1, K + 1):

          W = add[i][0] # 물품의 무게

          V = add[i][1] # 물품의 가치

          if W <= j:

             dp[i][j] = max(dp[i - 1][j], V + dp[i - 1][j - W])

          else:

             dp[i][j] = dp[i - 1][j]

 

print(dp[N][K])

코드 하나하나 설명 들어갑니다.

import sys

sys 모듈 : 시스템과 관련된 함수와 변수들을 제공하여 파이썬 프로그램이 운영 체제와 상호 작용하고 정보를 얻을 수 있게 도와줍니다. 

sys.stdin

sys.stdin : sys 모듈 내에 있는 표준 입력 스트림을 나타내는 객체입니다. 표준 입력 스트림은 사용자가 키보드로 입력하는 데이터를 읽어오는 용도로 사용됩니다.

input = sys.stdin.readline

sys.stdin.readline : 표준 입력 스트림에서 한 줄을 읽어오는 함수입니다. 이 함수를 호출하면 사용자가 입력한 데이터 중에서 한 줄을 읽어와 문자열로 반환합니다. 입력이 없을 때까지 기다릴 수 있습니다.

 map(int, input().split()

map() 함수는 여러 개의 이터러블을 인자로 받을 수 있으며, 이 경우 인자로 들어온 이터러블들의 각 요소를 함께 넘겨주어 함수를 적용합니다. 

--------------------------------

N, K = map(int, input().split())

 

물품의 수 = N, 버틸 수 있는 무게  = K를 입력받습니다.

add = [[0,0]]

add 객체에 각 물품무게, 가치의 합을 저장할 객체를 생성합니다.

dp = [[0] * (10001) for _ in range(101)

최대 가치를 저장할 객체입니다.(10001 = k + 1, 101 = N + 1이며 문제조건에 정의되어 있습니다,)

 

for i in range(1, N + 1):

W, V = map(int, input().split())

add.append([W, V])

반복문을 사용하여 물품의 무게 W, 물품의 가치 V를 입력받습니다.

 

for i in range(1, N + 1):

      for j in range(1, K + 1):

      W = add[i][0] # 물품의 무게

      V = add[i][1] # 물품의 가치

이차원 배열을 생성한뒤. 물품의 무게와 가치를 add에 각각 저장합니다.

if W <= j:

dp[i][j] = max(dp[i - 1][j], V + dp[i - 1][j - W])

else:

dp[i][j] = dp[i - 1][j]

if 물품의 무게가 현재 배낭의 무게보다 작거나 같을경우

dp[i][j] = max(dp[전 물품의 무게][현재 배낭의 무게], 물품의 가치 + dp[전 물품의 무게][현재 배낭의 무게 - 물품의 무게]

else 물품의 무게가 현재 배낭의 무게보다 클경우

dp[i][j] = dp[전 물품의 무게][현재 배낭의 무게]

print(dp[N][K])

최종적으로 dp[N][K]를 출력하면 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구할 수 있습니다.