[Python] 12865 - 평범한 배낭

[Gold V] 평범한 배낭 - 12865 

[문제 링크](https://www.acmicpc.net/problem/12865)

🗝️알고리즘 분류

• 다이나믹 프로그래밍
• 냅색 문제

---

💻문제 정의

가방에는 최대 K만큼의 짐을 실을 수 있다. 각 짐의 무게 W와 짐의 가치 V가 주어지고, 가치의 최댓값을 구하는 문제이다.

💡접근 및 설계

유명한 배낭 문제(Knapsack Problem)이다. 프로그래밍을 배운지 얼마 안되었을 때 접해본 개념이다. 기억을 더듬으며 문제를 해결해보았다.

 

다이나믹 프로그래밍인 만큼, 문제를 세분화 해서 보는것이 중요하다. 

현재의 짐을 담았을 때, 다음 짐을 담을 수 있는지를 판별, 담을 수 있다면 가치 합을 저장한다.

 

🗒️전체 코드

# 12865 평범한 배낭

import sys
input = sys.stdin.readline

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

bag = [[0, 0]]
for _ in range(N):
    bag.append(list(map(int, input().split())))

knapsack = [[0] * (K+1) for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, K+1):
        weight = bag[i][0] # 현재 짐의 무게
        value = bag[i][1] # 현재 짐의 가치

        if (j < weight): # j는 가방 무게의 한도
            knapsack[i][j] = knapsack[i - 1][j] # 현재 짐의 무게가 한도 보다 무거우면 넣을 수 없다. 따라서 이전에 넣은 짐의 가치를 그대로 가져옴 
        else: # 가방에 짐을 넣을 경우
            knapsack[i][j] = max(value + knapsack[i - 1][j - weight], knapsack[i - 1][j]) # (j - weight)무게의 가치와 현재 짐의 가치를 합해야 j번째가 된다.

print(knapsack[N][K])