[백준 12865번][골드5] 평범한 배낭 (파이썬)

---

문제출처

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

12865번: 평범한 배낭

---

문제를 스스로 해결하였는가? -> X

 문제를 읽자마자 프로그래머스의 피로도 문제와 비슷하다고 생각해서 바로 백트래킹으로 접근했다. 하지만 시간초과.. 문제의 조건을 살펴보니 피로도 문제는 배열의 길이가 1 < N < 9이여서 완전탐색이 가능했지만, 이 문제는 1 < N < 101라서 완전탐색을 하게 되면 시간초과가 난다. 문제의 알고리즘 힌트를 참고하여 dp로 접근했지만 이 방법 역시 1 < K < 100001라는 조건이 있어 O(K^2) 방법으로는 제한시간을 초과하게 된다. 구글링해보니 아주 유명한 냅색문제라 하더라.. 알고리즘에 대한 설명은 여러 블로그에 자세히 설명되어 있어서 따로 정리는 안하고 다음에 참고할 수 있도록 링크만 남겨야겠다. 링크

---

필요한 배경지식

• dp
• 냅색

---

주의할 점

• 준서가 버틸 수 있는 가방의 무게는 (0 < K < 100001)이다.
• 따라서 O(K^2) 방법으로는 제한시간을 통과 못한다.

---

실패 코드

시간초과가 난 코드다. 백준도 프로그래머스처럼 정확도 테스트와 효율성 테스트를 따로 검사했으면 좋겠다... 

import math
import sys
input = sys.stdin.readline
n, k = map(int, input().split(' '))
dp = [0] * (k+1)
for _ in range(n):
    w, v = map(int, input().split(' '))
    dp[w] = v

for i in range(1,k+1):
    tmp = []
    for j in range(math.ceil(i/2)):
        tmp.append(dp[j] + dp[i-j])
    dp[i] = max(tmp)
print(dp[-1])

---

성공 코드

 개인적으로 j를 배낭에 담을 수 있는 최대 무게라고 생각하니 이해하기 편했다. 입력받은 물건의 무게 w보다 배낭에 담을 수 있는 최대 무게 j가 작으면 입력받은 물건을 담지말고 넘어간다. (knap[i][j] = knap[i-1][j])

 반면 입력받은 물건의 무게가 배낭에 담을 수 있는 최대 무게보다 작으면(w>=j) 물건을 담았을 때 가치와 담지 않았을 때 가치를 비교해 큰 값을 선택하면 된다.

import sys
input = sys.stdin.readline
n, k = map(int, input().split(' '))
knap = [[0]*(k+1) for _ in range(n+1)]

for i in range(1,n+1):
    w, v = map(int, input().split(' '))
    for j in range(1,k+1):
        if j < w:
            knap[i][j] = knap[i-1][j]
        else:
            knap[i][j] = max(knap[i-1][j-w] + v,
                             knap[i-1][j])
print(knap[-1][-1])

---