[알고리즘 / 백준] 12865 - 평범한 배낭
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
문제는 위와 같으며 이 문제는 배낭의 무게가 0 ~ K 인 경우를 모두 확인하는 방식으로 문제를 풀 수 있습니다.
예제를 바탕으로 살펴보면 처음에는 0부터 7까지 모두 가치가 0인 배열로 초기화를 하고 이후 무게(w)와 가치(v)가 주어지면 w 보다 작은 무게의 경우는 기존 가치를 그대로 가져가고 w 보다 크거나 같을 때는 w 를 뺀 무게의 가치와 주어진 가치(v)를 더해 이전 가치와 비교해 더 큰 값으로 가치를 정합니다.
그림으로 보면 다음과 같습니다.
1. w = 6, v = 13 인 경우
- 0 ~ 5 까지는 기존 가치 그대로 추가
- 6 인 경우 기존 무게 6의 가치(0) 와 무게 0의 가치(0) + 주어진 가치(13) 중 더 큰 가치로 지정 => 13
- 7 인 경우도 기존 무게 7의 가치(0) 와 무게 1의 가치(0) + 주어진 가치(13) 중 더 큰 가치로 지정 => 13
2. w = 4, v = 8 인 경우
- 0 ~ 3 까지는 기존 가치 그대로 추가
- 4 인 경우 기존 무게 4의 가치(0) 와 무게 0의 가치(0) + 주어진 가치(8) 중 더 큰 가치로 지정 => 8
- 5 인 경우 기존 무게 5의 가치(0) 와 무게 1의 가치(0) + 주어진 가치(8) 중 더 큰 가치로 지정 => 8
- 6 인 경우 기존 무게 6의 가치(13) 와 무게 2의 가치(0) + 주어진 가치(8) 중 더 큰 가치로 지정 => 13
- 7 인 경우 기존 무게 7의 가치(13) 와 무게 3의 가치(0) + 주어진 가치(8) 중 더 큰 가치로 지정 => 13
3. w = 3, v = 6 인 경우
- 0 ~ 2 까지는 기존 가치 그대로 추가
- 3 인 경우 기존 무게 3의 가치(0) 와 무게 0의 가치(0) + 주어진 가치(6) 중 더 큰 가치로 지정 => 6
- 4 인 경우 기존 무게 4의 가치(8) 와 무게 1의 가치(0) + 주어진 가치(6) 중 더 큰 가치로 지정 => 8
- 5 인 경우 기존 무게 5의 가치(8) 와 무게 2의 가치(0) + 주어진 가치(6) 중 더 큰 가치로 지정 => 8
- 6 인 경우 기존 무게 6의 가치(13) 와 무게 3의 가치(0) + 주어진 가치(6) 중 더 큰 가치로 지정 => 13
- 7 인 경우 기존 무게 7의 가치(13) 와 무게 4의 가치(8) + 주어진 가치(6) 중 더 큰 가치로 지정 => 14
4. w = 5, v = 12 인 경우
- 0 ~ 4 까지는 기존 가치 그대로 추가
- 5 인 경우 기존 무게 5의 가치(8) 와 무게 0의 가치(0) + 주어진 가치(12) 중 더 큰 가치로 지정 => 12
- 6 인 경우 기존 무게 6의 가치(13) 와 무게 1의 가치(0) + 주어진 가치(12) 중 더 큰 가치로 지정 => 13
- 7 인 경우 기존 무게 7의 가치(14) 와 무게 2의 가치(0) + 주어진 가치(12) 중 더 큰 가치로 지정 => 14
따라서 결과적으로 테이블의 가장 끝 무게의 가장 끝 가치가 정답이 됩니다.
파이썬 코드는 다음과 같습니다.
from sys import stdin
n, k = map(int, stdin.readline().split())
dp = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w, v = map(int, stdin.readline().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[-1][-1])
자바 코드는 다음과 같습니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] nk = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int[][] dp = new int[nk[0] + 1][nk[1] + 1];
for (int i = 1; i < nk[0] + 1; i++) {
int[] wv = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
for (int j = 1; j < nk[1] + 1; j++) {
if (j < wv[0]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wv[0]] + wv[1]);
}
}
}
System.out.println(dp[nk[0]][nk[1]]);
}
}