동적 프로그래밍 : 평범한 배낭(백준 12865번)

▶ 문제 : https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

##### 문제 #####
# 이 문제는 아주 평범한 배낭에 관한 문제이다.
# 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 
# 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 
# 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
# 준서가 여행에 필요하다고 생각하는 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)가 주어진다.
# 입력으로 주어지는 모든 수는 정수이다.

##### 출력 #####
# 한 줄에 배낭에 넣을 수 있는 물건들의 가치 합의 최댓값을 출력한다.

 

▶ 접근 방법

냅색 알고리즘(Knapsack Algorithm)의 기본 유형 문제였다.
냅색 알고리즘은 동적 프로그래밍과 백 트랙킹 두 가지 방식으로 해결할 수 있는데
아래 풀이에서는 동적 프로그래밍을 활용하였다.

최대 무게를 기준으로 테이블을 하나 만들고,
해당 테이블에 가능한 무게 조합들의 최대 가치들을 하나 씩 채워나갔다. 

 

▶ 풀이 코드

import sys

# N : 물품의 수, K : 최대 무게
N, K = map(int, sys.stdin.readline().split())

# 무게 테이블을 만든다.
table = [0] * (K + 1)


# 물품들을 하나 씩 살펴본다.
for _ in range(N) :
    # 물품의 무게와 가치를 입력 받는다.
    weight, value = map(int, sys.stdin.readline().split())

    # 만약 입력받은 물품의 무게가 견딜 수 있는 최대 무게보다 크다면 아래 과정 진행하지 않는다.
    if weight > K :
        continue
    
    
    # 가능한 무게를 하나 씩 확인한다.
    for possible_weight in range(K, 0, -1) :
        # 가능한 무게와 입력 받은 물품의 무게를 더한 것이 최대 무게를 넘지 않고,
        # 가능한 무게의 value가 0이 아니라면 
        if possible_weight + weight <= K and table[possible_weight] != 0:
            # 가능한 무게와 입력 받은 물품의 무게를 더한 무게의 value는
            # 기존의 다른 조합으로 해당 무게의 value를 도출한 값과, 지금의 조합을 비교해서 최대 인 것으로 바꾼다.  
            table[possible_weight + weight] = max(table[possible_weight + weight], table[possible_weight] + value)
    
    # 조합 없이 물품 1개만 넣었을 때의 value는 다음과 같이 넣어준다.
    table[weight] = max(table[weight], value)
    print(table)
    
print(max(table))

 

▶ 관련 링크

2021.11.25 - [알고리즘] - 동적 프로그래밍(Dynamic Programming)이란?

2021.11.25 - [알고리즘] - 동적 프로그래밍 : 피보나치 수 2(백준 2748번)

2021.11.25 - [알고리즘] - 동적 프로그래밍 : 01타일(백준 1904번)

2021.11.26 - [알고리즘] - 동적 프로그래밍 : 평범한 배낭(백준 12865번)

2021.11.27 - [알고리즘] - 동적 프로그래밍 : 동전(백준 9084번)

2021.11.27 - [알고리즘] - 동적 프로그래밍 : LCS(백준 9251번)

2021.11.27 - [알고리즘] - 동적 프로그래밍 : 가장 긴 증가하는 부분 수열(백준 11053번)