대학교/Algorithm
[백준 12865] 평범한 배낭
SWKo
2020. 9. 11. 21:53
0. 제목
- 백준 12865 평범한 배낭
- BOJ 12865 평범한 배낭
- 파이썬 12865 평범한 배낭
- Python 12865 평범한 배낭
1. 문제
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
2. 풀이
- dp[i][j] = 배낭에 넣은 물품의 무게 합이 j일 때 얻을 수 있는 최대 가치
- 각 물품의 번호 i에 따라서 dp[i][j]를 갱신한다.
- 1부터 k까지 증가하는 변수 j가 입력된 무게보다 작은 경우에는 전에 입력된 가치인 dp[i-1][j]를 그대로 가져온다.
- j가 입력된 무게보다 크거나 같은 경우에는 max(dp[i - 1][j], dp[i - 1][j - w] + v) 의 값이 dp[i][j]의 값이 된다.
- 이 문제에서는 (4, 8), (3, 6)일 때가 가치합의 최댓값인데, 세번째 물건인 (3,6)이 들어왔을 때 dp[3][7] = 14 로 갱신이 된다.
- 반복문을 마친 후 dp[n][k]이 가치합의 최댓값이 된다.
3. 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
|
n, k = map(int, input().split())
dp = [[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:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
print(dp[n][k])
|