백준 12865번: 평범한 배낭(Python)
문제
입출력
- 예제 입력
4 7
6 13
4 8
3 6
5 12 - 예제 출력
14
풀이
0-1 Knapsack 알고리즘
배낭 문제(Knapsack Problem 냅색 프라블럼)는 조합 최적화의 유명한 문제이다.
간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.
이 배낭문제는 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0 이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem), 짐을 쪼갤 수 없는 경우의 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라 부른다.
위키백과 https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C
dp로 해결할 수 있다
소스코드
import sys
N, K = map(int, sys.stdin.readline().rstrip().split())
def knapsack(N, K):
ks = [[0 for _ in range(K+1)] for _ in range(N+1) ]
for n in range(1, N+1):
for w in range(0, K+1):
value[n-1]
if weight[n-1] <= w: # 물건의 무게가 배낭에 담을 수 있는 최대 무게보다 작거나 같음
# 물건을 넣었을 때의 가치와 물건을 넣지 않았을 때의 가치 중 큰 값을 선택
ks[n][w] = max(ks[n-1][w-weight[n-1]] + value[n-1], ks[n-1][w])
else: # 물건의 무게가 배낭에 담을 수 있는 최대 무게보다 큼
ks[n][w] = ks[n-1][w] # n-1번째 물건까지 담았을 때의 가치
return ks[N][K]
value = []
weight = []
for i in range(N):
w, v = map(int, sys.stdin.readline().rstrip().split())
weight.append(w)
value.append(v)
print(knapsack(N, K))
N : 물건의 수
K : 버틸 수 있는 무게
value : 물건들의 가치
weight: 물건들의 무게
ks[n][w] : n은 물건 번호, w는 배낭이 견디는 최대 무게
n번째 물건까지 배낭에 최대 w까지 담을 수 있다. 이 때 배낭에 담을 수 있는 물건들의 가치 합의 최댓값을 의미한다.
풀이 참고
[환상빛 별하늘] Reb∞t Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)
Author And Source
이 문제에 관하여(백준 12865번: 평범한 배낭(Python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kayoung0/백준-12865번-평범한-배낭Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)