[Gold V] 평범한 배낭 - 12865
성능 요약
메모리: 52664 KB, 시간: 192 ms
분류
다이나믹 프로그래밍(dp), 배낭 문제(knapsack)
문제 설명
이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.
입력
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.
입력으로 주어지는 모든 수는 정수이다.
출력
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.
dp를 연습하기 좋은 문제인 것 같다.
아예 Knapsack Problem이라는 이름으로 알고리즘이 있다는 걸 처음 알았다. 참고 링크
dp를 활용하는 것은 알았는데, 단순히 이전 값의 최대값으로 dp를 채워가면, n-1번째의 최대값이 n번째의 최대값과 같지 않을 수 있다는 문제점이 있었다.
그렇다고 완전 탐색으로 모든 경우의 수를 탐색하면 시간 초과가 났다.
방법을 찾아보니, dp의 배열에 무게(1~K)를 행 또는 열로 삼는 것이 핵심이었다.
K번째의 dp 값은 해당 idx에 K의 무게 내에서 만들어낼 수 있는 최대의 가치였다.
dp값을 업데이트할 때 경우의 수는 두 가지가 가능하다.
- 해당 물건의 무게(Wi)가 그 배열에서의 무게 (Wk)보다 클 경우
이 때는 해당 물건을 담을 수 없으므로 이전 dp값을 그대로 가져온다.
dp[i][k] = dp[i-1][k]
- 해당 물건의 무게(Wi)가 그 배열에서의 무게 (Wk)보다 작을 경우
이때는 해당 물건을 넣은 값과, 이전 dp값 중 큰 값을 가져온다.
해당 물건을 넣었을 때의 최대값은, 무게 Wk에서 Wi를 뺐을 때의 dp값에 해당 물건의 가치를 더한 값이었다.
이 조건을 생각하는 게 어려웠다. n번째에 dp를 진행할 때, n-1까지는 해당 무게에서의 최대 가치가 이미 저장되어 있으므로, Wk에서 Wn를 뺀 dp값이 n번째 물건을 넣었을 때의 최대 가치였다.
dp[i][k] = Math.max(value[i]+dp[i-1][k-wi], dp[i-1][k]);
package Gold.g5;
import java.util.Scanner;
public class BOJ_12865_평범한배낭 {
static int N, K;
static int[] value;
static int[] weight;
static int[][] dp; // 0에 weight, 1에 value 저장
static int ans = 0;
static boolean[] visited;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
K = sc.nextInt();
value = new int[N + 1];
weight = new int[N + 1];
visited = new boolean[N];
dp = new int[N + 1][K + 1]; // row는 N, col은 K(무게)
for (int i = 1; i <= N; i++) {
weight[i] = sc.nextInt();
value[i] = sc.nextInt();
}
for (int n = 1; n <= N; n++) {
// n번째 값에 대해 dp값 구하기
for (int w = 1; w <= K; w++)
if (weight[n] <= w) { // 물건 추가 가능
dp[n][w] = Math.max(value[n] + dp[n - 1][w - weight[n]], dp[n - 1][w]);
} else // 물건 추가 불가능
dp[n][w] = dp[n - 1][w];
}
System.out.println(dp[N][K]);
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 2579 - 계단 오르기 (자바/Java) : DP (1) | 2022.09.23 |
---|---|
[백준] 12100 - 2048 (Easy) (자바/Java) (1) | 2022.09.22 |
[백준] 17069 - 파이프 옮기기 2 (자바/Java) (0) | 2022.09.22 |
[백준] 1759 - 암호 만들기 (자바/Java) (1) | 2022.09.21 |
[백준] 11444 - 피보나치 수 6 (1) | 2022.09.20 |