백준 알고리즘 12865: 평범한 배낭(Python)

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

12865번: 평범한 배낭

---

문제 해결을 위한 과정

이 문제의 경우 dp를 이용한 냅색 알고리즘입니다. 입력받은 물품들을 정렬하지 않는 이유는 dp는 순서에 의존하지 않는 최적화 문제이기 때문입니다. 따라서 순서를 고려하지 않기 위해 정렬을 하지 않는 것입니다. 표를 그리면 다음과 같습니다. 

	0	1	2	3	4	5	6	7
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4	0	0	0	6	8	12	13	14

행은 탐색한 배낭의 번호를, 열은 가져갈 수 있는 무게를 나타냅니다. 이렇게 하게 되면 다음과 같은 점화식을 얻을 수 있습니다.

 

if 현재 열의 무게 < 현재 탐색한 배낭의 무게 :

    graph[i][j] = graph [i-1][j]

else:

    graph [i][j] = max(graph [i-1][j], value + graph[i-1][j-weight])

 

이를 소스코드로 작성하면 다음과 같습니다.

---

소스코드

n, k = map(int, input().split())
graph = [[0] * (k+1) for _ in range(n+1)]
obj = []
for _ in range(n):
  a, b = map(int, input().split())
  obj.append((a, b))

for i in range(1, n + 1):
  for j in range(1, k + 1):
    weight = obj[i-1][0]
    value = obj[i-1][1]
    if j < weight:
      graph[i][j] = graph[i-1][j]
    else:
      graph[i][j] = max(graph[i-1][j], value + graph[i-1][j-weight])
print(graph[n][k])