[BOJ_Python] 12865. 평범한 배낭

문제

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

 

사용 알고리즘

0/1 Knapsack

 

풀이

고려사항

1. 현재 부분 집합 기준에 기준 물건이 들어갈 수 있는지

2. 들어갈 수 있다면 현재 부분 집합에 기준 물건을 넣을지 여부

 

후기

1. 이 문제는 배낭문제(0/1 Knapsack)의 가장 기본 틀이다.

2. 물건을 하나씩 차례로 기준을 잡으며 그 때, 무게 별 부분 집합을 만들 때의 경우를 확인한다.

이때, 먼저 해당 물건만 담을 때도 그 무게에 벗어나는지 여부를 확인한다.

무게에 벗어나면 담지 못하고,

무게에 벗어나지 않는다면 담을지 여부를 판단한다.

 

3. 배낭 문제의 가장 기초 문제이기 때문에 연습해보기 좋은 문제였다.

 

코드

import sys
input = sys.stdin.readline

# 물품 수, 최대 무게
N, M = map(int, input().split())

# 물건 리스트(무게, 가치)
suff = [[0, 0]]
for _ in range(N):
    suff.append(list(map(int, input().split())))

# knapsack 정보 업데이트
knapsack = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(1, N + 1):  # 물품 관련
    for j in range(1, M + 1):  # 현재 배낭 무게 관련
        w, v = suff[i][0], suff[i][1]

        # 현재 물품만 담는다고 해도 담지 못하는 경우
        if j < w:
            knapsack[i][j] = knapsack[i - 1][j]
        # 현재 물품을 가지고 판단 진행
        else:
            # 현재 물품을 넣지 않는 경우, 넣는 경우 비교
            knapsack[i][j] = max(knapsack[i - 1][j], v + knapsack[i - 1][j - w])
print(knapsack[N][M])

 

결과