[DP] 백준 12865번: 평범한 배낭

KimRiun·2021년 11월 23일
0

알고리즘_문제

목록 보기
23/26

사용 언어: python 3.9.5

❓ Problem

문제 설명

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

난이도

골드5

🚩 Solution

시도 01)

1. 접근법

동적 프로그래밍으로 접근한다.

  1. input

    물건 개수 : 4

    배낭 무게 : 7

    물건 1: 무게 6, 가치 13

    물건 2: 무게 4, 가치 8

    물건 3: 무게 3, 가치 6

    물건 4: 무게 5, 가치 12

  1. dp 테이블과 점화식

    dp 테이블(세로축:물건/가로축:배낭 무게/값:최대가치) 에는 가로축의 배낭 무게에 따라 세로축 물건을 누적해서 고려하였을 때 가치의 최대값을 저장한다. 가치의 최대값을 구하므로 세로축 물건을 누적해서 고려할 때, 이전 물건을 포함할 수도 있고 아닐 수도 있고, 현재 물건이 포함될 수도 있고 아닐 수도 있는 것이다.

    dp 테이블을 채우는 방식은 아래와 같다.

    i : 물건

    j : 배낭 무게

    arr[[0,0],[6,13][4,8],[3,6],[5,12]] : 무게,가치를 담은 배열

    현재 dp 테이블의 위치를 dp[i][j]라 하자.

    dp[i][j] 는 아래 두 값 중 최대를 택한다.

    dp[i-1][j] : 현재 물건을 배낭에 넣지 않을 경우 가치의 최대값이다. 현재 물건은 넣지 않으므로 이전 물건까지에서 구한 최대값과 동일하다.

    dp[i-1][j-arr[i][0]]+arr[i][1] : 현재 물건을 배낭에 넣을 경우 가치의 최대값이다. 현재 물건을 배낭에 넣을 것이기 때문에 배낭 무게에서 현재 물건의 무게를 뺐을 때 가치의 최대가 얼마였는지 dp 테이블에서 찾고, 그 값에 현재 물건의 가치를 더해준다.

    따라서 dp[i][j] = max(dp[i-1][j], dp[i-1][j-arr[i][0]]+arr[i][1]) 이다.

    배열을 사용할 때는 인덱스 벗어나지 않게 주의하자(j-arr[i][0]는 인덱스를 벗어나지 않는지 조건문으로 확인해야 한다.)

2. 코드

# n : 물건 개수(= arr 크기)
# weight : 배낭이 담을 수 있는 무게
# arr : 물건 무게, 가치의 쌍을 저장하는 물건 배열
def solution(n: int, weight: int, arr: list[list]):
    dp = [[0 for _ in range(weight+1)] for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(weight+1):
            if j-arr[i][0] >= 0:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-arr[i][0]]+arr[i][1])
            else:
                dp[i][j] = dp[i-1][j]
    
    answer = 0
    for i in dp:
        answer = max(answer, max(i))
    
    return answer

import sys
input = sys.stdin.readline
n, weight = map(int, input().split())

arr = []
arr.append([0, 0])
for _ in range(n):
    arr.append(list(map(int, input().split())))
print(solution(n, weight, arr))

3. 결과

성공

메모리: 226652 KB

시간: 5676 ms

profile
Java, Python

0개의 댓글