[백준] 12865번 평범한 배낭 (냅색 문제)

사용 언어 - Python3

문제 -  12865번 평범한 배낭

냅색 Knapsack 문제 : 여러 물건이 있을 때, 특정 조건을 만족하는 조합 구하기

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

12865번: 평범한 배낭

 

 

정답

1. 완전 탐색적 재귀함수 => 시간 초과

def recur(idx, w, v)

def recur(idx,w,v):
    global answer
    
    if w > k: # 버틸 수 있는 k 무게 초과시 무시
        return
    if idx == n: # 모든 물품 사용
        answer = max(v,answer)
        return
    
    # 해당 물품 넣은 경우
    recur(idx+1, w+list_a[idx][0], v+list_a[idx][1])
    # 해당 물품 안 넣은 경우
    recur(idx+1, w, v)
    
n, k = map(int,input().split()) # 물품의 수, 버틸 수 있는 무게
# 각 물건의 무게 w, 해당 물건의 가치 v
list_a = [list(map(int,input().split())) for _ in range(n)]
answer = 0
recur(0,0,0) #물품 번호 0, 물건의 무게 0, 물건의 가치 0에서 시작
print(answer)

 

2. 탑다운 DP로 해야 시간 초과 안뜸!

2차원 DP 컴퓨터에 해당 경우의 가치를 기억해주기

dp 2차원 리스트 생성 -> 각 물품번호마다 가치를 저장해준다.

무게 최대값 100,000 / 물건개수 n개

 

해당 물품 넣은 경우와 안넣은 경우 중 최대 가치를 dp[idx][w]에 기억해준다.

- 물품 넣은 경우의 가치 recur(idx+1, 물품 무게) + 물품 가치

- 물품 안넣은 경우의 가치 recur(idx+1, 물품 무게)

 

- 버틸 수 있는 무게를 초과시 무시

- n개 물품 모두 다 돌면 return 0

- 이미 계산된 경우, 계산안함 dp[idx][w]

 

print(dp[0][0])

def recur(idx,w):    
    if w > k: # 버틸 수 있는 k 무게 초과시 무시
        return -9999999999
    if idx == n: # 모든 물품 사용
        return 0
    if dp[idx][w] != -1:
        return dp[idx][w]

    # 해당 물품 넣은/안넣은 경우
    dp[idx][w] = max(recur(idx+1, w+list_a[idx][0]) + list_a[idx][1],recur(idx+1, w))
    
    return dp[idx][w]

n, k = map(int,input().split()) # 물품의 수, 버틸 수 있는 무게
# 각 물건의 무게 w, 해당 물건의 가치 v
list_a = [list(map(int,input().split())) for _ in range(n)]
dp = [[-1 for _ in range(100001)] for _ in range(n)]
recur(0,0) #물품 번호 0, 물건의 무게 0
print(dp[0][0])

 

 

3. 바텀업 DP 

탐다운을 for문으로 만들어주면 점화식 도출된다.

바텀업이라 idx-1로 한개씩 줄어들면서 반복해준다.

=> 리스트 범위 1부터 시작해야함. 주의하기

print(dp[n][k]) 마지막 값이 답이다.

n, k = map(int, input().split())

list_a = [(0, 0)]
for _ in range(n):
    w, v = map(int, input().split())
    list_a.append((w, v))

dp = [[0] * (k + 1) for _ in range(n + 1)]

for idx in range(1, n + 1):
    for weight in range(1, k + 1):        
        if weight < list_a[idx][0]:
            dp[idx][weight] = dp[idx - 1][weight]
        else:
            dp[idx][weight] = max(dp[idx - 1][weight - list_a[idx][0]] + list_a[idx][1],dp[idx - 1][weight])

print(dp[n][k])

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/12865_%ED%8F%89%EB%B2%94%ED%95%9C%EB%B0%B0%EB%82%AD.py

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/12865_%ED%8F%89%EB%B2%94%ED%95%9C%EB%B0%B0%EB%82%AD1.py

 

• 냅색 문제

https://chanhuiseok.github.io/posts/improve-6/

[알고리즘 트레이닝] 5장 - 동적계획법과 냅색(Knapsack) (백준 12865번 평범한 배낭 문제로 살펴보기)