개발일지/Algorithm
백준 - 12865 평범한 배낭 [DP][탑다운][바텀업]
E-room
2023. 10. 10. 17:34
728x90
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
1. 문제 요약
물품의 수 N, 버틸 수 있는 무게 K, 각 물건의 무게 W, 물건의 가치 V가 주어집니다.
물건들을 가장 많이 가져갈 수 있는 조합을 구하시오.
2. 접근 방법
먼저 완전탐색으로 모든 경우의 수를 다 때려 넣어봅니다.
def solution(idx, w, v):
global answer
if w > K:
return
if idx == N:
answer = max(answer, v)
return
solution(idx+1, w+items[idx][0], v+items[idx][1])
solution(idx+1, w, v)
시간과 메모리가 충분하다는 가정하에 해결할 수 있지만, 해당 문제는 시간초과가 발생하므로 최적화를 진행해야 합니다.
위 풀이를 살짝만 수정해 주면 탑다운 DP방식으로 전환할 수 있습니다.
가장 뒤에서부터 이전 방법과 비교하여 더 큰 값을 기록하는 방식을 사용합니다.
탑다운 방식에서 다시 수정하여 일반적으로 잘 알려진 방식인 바텀업 방식으로 변경해 보겠습니다.
3. 파이썬 (탑다운)
dp = [[-1] * (K+1) for _ in range(N)]
def solution(idx,w):
if w > K:
return -1e9
if idx == N:
return 0
if dp[idx][w] != -1: # 방문했는지 여부를 확인하는 핵심 부분
return dp[idx][w]
dp[idx][w] = max(
solution(idx+1,w+items[idx][0]) + items[idx][1], # 사용하거나
solution(idx+1,w) # 사용하지 않거나
)
return dp[idx][w]
4. 자바 (바텀업)
static private int solution(int n, int k, int[][] items) {
int[][] dp = new int[n + 1][k + 1];
for (int index = 1; index <= n; index++) {
for (int weight = 1; weight <= k; weight++) {
if (weight < items[index - 1][0]) { // 무게 체크하는 부분 (위 코드에서 if문 부분)
dp[index][weight] = dp[index - 1][weight];
} else {
dp[index][weight] = Math.max(
dp[index - 1][weight], // 사용하지 않거나
dp[index - 1][weight - items[index - 1][0]] + items[index - 1][1] // 사용하거나
);
}
}
}
return dp[n][k];
}
5. 전체 코드
728x90