[백준] 평범한 배낭 - 자바(Java)
문제 링크
https://www.acmicpc.net/problem/12865
문제 설명
이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 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)가 주어진다.
입력으로 주어지는 모든 수는 정수이다.
출력
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.
입출력 예
| 입력 | 출력 |
| 4 7 6 13 4 8 3 6 5 12 |
14 |
문제 풀이
[고려사항]
1. 시간 복잡도
물품의 조합별 최대 가치 누적값을 구해야하는데, 조합으로 하면 물품 개수(N)가 최대 100개이므로 n개 중 r개로 풀면 시간 복잡도가 O(n^r)이 되기때문에 그냥 조합으로 풀면 안된다.
2. dp 배열의 구성
결론부터 말하면 이 문제는 DP로 구현했는데, 조건을 2개를 두어 다차원 DP로 구현했다.
이때 행과 열을 각각 어떤걸로 정하냐에 따라 시간차이가 (미미하지만) 나길래 기록해둔다.
자세한건 아래 구현방법에 추가하였으니 궁금하다면 참고하면 되겠다!
[알고리즘, 구현방법]
기본적인 개념은 조합으로 생각하면서 최적화시키는 방향으로 해야할 것으로 보여, DP로 구현했다.
✅ 정답
DP로 풀어야겠다는 결론은 나왔는데, DP를 정의하기가 어려웠다.
DP 요소의 기준을 물품의 번호로 두거나(i번째 물품까지 확인했을때 최대 가치), 중량의 기준으로 두거나(i kg까지 확인했을때 최대가치) 라는 조건들을 둬도 이외 조건에 따라 값이 달라질 수 있다. 가방의 무게가 같더라도 물품 조합에 따라 최대 가치가 달라지는 등의 문제가 생긴다.
그래서 무게와 물품, 두 가지로 기준을 두어 2차원 배열의 DP로 구현했다.
행에는 물품, 열에는 배낭의 최대 무게를 두고(dp[물품][무게]), 해당 무게에 해당하는 최대 가치를 계산한다.
즉, dp[i][j] = i번째 물품까지의 배낭의 무게 j를 담았을때의 최대 가치이다.
*편의상 0번 행, 0번 열은 쓰지 않는다.
| 물품 / 무게 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 (6kg, 13) | 0 | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
| 2 (4kg, 8) | 0 | 0 | 0 | 0 | 8 | 8 | max(0+8, 13) = 13 | max(0+8, 13) = 13 |
| 3 (3kg, 6) | 0 | 0 | 0 | 6 | max(0+6, 8) = 8 | max(0+6, 8) = 8 | max(0+6, 13) = 13 | max(8+6, 13) = 14 |
| 4 (1kg, 12) | 0 | 12 | 12 | max(0+12, 6) = 12 | max(6+12, 8) = 18 | max(8+12,13) = 20 | max(8+12,13) = 20 | max(13+12,14) = 25 |
문제 예시 1번을 조금 바꿔서 예를 들어보자.
무게가 3kg일때를 보면, 1, 2번 물품까지는 가방에 담을 무게 3kg을 초과하기 때문에 조건에 맞지않아 넣을 수 없어서 가치가 0이 된다. 3번째 물품은 3kg이라서 조건에 부합하여 해당 물품의 가치인 6을 할당한다.
그리고 (4,3)는 4번째 물품까지 배낭에 3kg을 넣을때, 최대 가치 값을 할당해야한다.
그런데 여기서 (3,3)에서 이미 최대 3kg이 찬 상태이므로 1kg인 4번 물품을 담으면서 최대 가치값을 구하려면 현재 3kg에서 4번 물품의 무게인 1kg을 뺀 (1) 2kg일때 3번 물품까지의 합과 4번 물품의 가치를 더한 값, (2) 3kg일때의 3번 물품까지의 합을 비교해서 최댓값을 넣어야한다.
즉, dp[4][3] = max(dp[3][2] + 물품[4].value, dp[3][3]) 으로 계산해야한다.
같은 무게라 할지라도 물품 조합에 따라 최대 가치가 바뀔 수 있기 때문이다.
그렇게하면 dp[3][2] = 0 , 물품[4].value = 12 의 합은 12, dp[3][3]은 6이므로 최대값 12가 할당된다.
i번째 물품 무게를 weight, 가치를 value라 했을때 일반 점화식은 아래와 같이 나오게된다.
dp[i][j] = max(dp[i - 1][j- weight] + value , dp[i-1][j])j번째 물품까지 i kg을 넣을 수 있을때 최대 가치 합은 (i-1)번째까지의 (j-(i번째 물품의 무게)) kg일 때의 가치 + i번째 물품의 가치 vs (i-1)번째 물품까지의 j kg의 물품의 가치 중 큰 값이다.
dp 배열을 모두 계산한 후에는 N번 물품까지의 최대 K kg 최대 가치인, dp[N][K]을 반환하면 된다.
💡 배열의 구성 방식
위 dp 배열에서 행과 열을 어떤 기준으로 잡느냐에 따라 코드를 제출했을때, 속도 차이가 있다는 것을 확인했다.
40ms정도의 차이이지만 같은 코드로 수행했는데도 배열의 행, 열 기준에 따라 속도 차이가 발생해서 한번 알아보았다.
2차원 배열은 메모리에서 저장될 때 행 우선(row-major) 방식으로 저장된다.
예를 들어 int[][] arr = new int[3][3] 배열의 해시 코드를 확인해보면 아래와 같다.
Row 0 hash code: 918221580
arr[0][0] = 0 (hash code: 918221580)
arr[0][1] = 1 (hash code: 918221580)
arr[0][2] = 2 (hash code: 918221580)
Row 1 hash code: 603742814
arr[1][0] = 3 (hash code: 603742814)
arr[1][1] = 4 (hash code: 603742814)
arr[1][2] = 5 (hash code: 603742814)
Row 2 hash code: 1067040082
arr[2][0] = 6 (hash code: 1067040082)
arr[2][1] = 7 (hash code: 1067040082)
arr[2][2] = 8 (hash code: 1067040082)행을 기준으로 Hash Code가 같은 것을 알 수 있다.
메모리에 행 우선 방식으로 저장되어있기때문에 배열에 접근할 때, 행을 고정하고 열을 이동시키면서 접근하는 방식이 더 효율적이다.
이제 두 방식의 차이를 살펴보자.
1. dp[무게][물품] 으로 했을때, 200ms
for (int i = 1; i <= k; i++) { // 무게 i
for (int j = 1; j <= n; j++) { // 물품 번호 j
if (i >= W[j]) dp[i][j] = Math.max(dp[i-W[j]][j-1] + V[j], dp[i][j-1]);
else dp[i][j] = dp[i][j-1];
}
}이 방식은 무게를 행으로 두고있고, 무게 i 가 변화할 때마다 해당 행 전체를 연속적으로 접근하지 않고 열단위로 접근한다.
dp[i][j]에 값을 할당하기 위해 i 가 1부터 k 까지 증가하면서 dp[i-W[j]][j-1]와 dp[i][j-1]을 참조하기 때문에 메모리 접근이 불연속적이다.
즉, dp[1][j], dp[2][j], ... , dp[k][j] 식으로 접근하게 된다.
2. dp[물품][무게] 으로 했을때, 160ms
for (int i = 1; i <= n; i++) { // 물품 번호 i
for (int j = 1; j <= k; j++) { // 무게 j
if (W[i] <= j) dp[i][j] = Math.max(dp[i-1][j-W[i]] + V[i], dp[i-1][j]);
else dp[i][j] = dp[i-1][j];
}
}이 방식은 물품을 행으로 두고있고, 물품 i 가 변화할 때마다 해당 행 전체를 연속적으로 접근한다.
dp[i][j]에 값을 할당하기 위해 i 가 1부터 n까지 증가하면서 dp[i-1][j-W[i]]와 dp[i-1][j]를 참조하기 때문에 메모리 접근이 연속적이다.
즉, dp[i][1], dp[i][2], ... , dp[i][k] 식으로 접근하게 된다.
따라서 메모리 접근이 행 기준으로 이루어져서 연속적인 2번째 코드가 캐시 효율이 높아서 더 좋은 성능을 가져 빠르게 실행된다.
X 1차 생각
처음에는 각 물건들의 조합별 가치를 계산해서 최댓값을 갱신하였다.
import java.io.*;
import java.util.*;
public class Main {
static int k;
static boolean[] checked;
static int max = 0;
static List<Product> list = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
for (int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine(), " ");
list.add(new Product(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
}
checked = new boolean[n];
for (int i=0; i<=n; i++) {
combination(0, n, i, 0, 0);
}
System.out.println(max);
}
public static void combination(int start, int n, int r, int w, int v) {
if (r == 0) {
if (w > k) return;
max = Math.max(max, v);
return;
}
for (int i=start; i<n; i++) {
int weight = list.get(i).w;
int value = list.get(i).v;
if (!checked[i]) {
checked[i] = true;
combination(i+1, n, r-1, w + weight, v + value);
checked[i] = false;
}
}
}
}
class Product {
int w;
int v;
public Product(int w, int v) {
this.w = w;
this.v = v;
}
}근데 이렇게 하니 시간 초과가 발생했다. 시간 복잡도를 계산해보니 N개중 r개를 선택하는 combination 을 수행하면 O(N^r).. n과 r은 최대 100이므로 시간 초과가 되지 않으면 이상할 정도였다..
그래서 값을 누적하면서 구현해야겠다고 생각했고, DP 로 문제를 다시 풀었다.
[풀이 과정]
- 물품 무게와 가치를 각 배열에 저장 (W, V)
- dp[물품][무게] 를 행을 기준으로 순회하면서 점화식으로 값 할당
- 각 물품의 무게가 현재 무게(j)보다 작거나 같을 경우에만 최댓값 비교
- 이외 경우엔 이전 값인 dp[i-1][j]를 할당
- dp 배열의 마지막 값 출력
정답 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
// 물품 무게, 가치 저장
int[] W = new int[n+1];
int[] V = new int[n+1];
for (int i=1; i<=n; i++) {
st = new StringTokenizer(br.readLine(), " ");
W[i] = Integer.parseInt(st.nextToken());
V[i] = Integer.parseInt(st.nextToken());
}
// DP로 최대 가치 계산
int[][] dp = new int[n+1][k+1]; // 0번 행, 0번 열은 사용하지 않음
for (int i=1; i<=n; i++) { // i: 물품
for (int j=1; j<=k; j++) { // j: 무게
// 각 물품의 무게가 현재 무게(j)보다 작거나 같을 경우에만 최댓값 비교
if (W[i]<=j) dp[i][j] = Math.max(dp[i-1][j-W[i]] + V[i], dp[i-1][j]);
else dp[i][j] = dp[i-1][j];
}
}
System.out.println(dp[n][k]);
}
}