- https://www.acmicpc.net/problem/12865
- https://github.com/kyukong/Algorithm/tree/main/백준/Gold/12865. 평범한 배낭
주어진 입력의 정보들 중 버틸 수 있는 무게 안에서 최대의 가치를 구하는 문제이다.
여러 개의 물건들의 가치 누적합을 구해야 하므로 dp 를 이용하였다.
이전의 가치합에서 현재의 가치합, 앞으로의 가치합을 구해야 하므로 dp 에는 현재 무게의 가치합을 관리한다.
실패1: 입력받은 순서에 의존
import java.util.*;
import java.io.*;
public class Main {
private static int n;
private static int max;
private static int[][] dp;
private static int result = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
max = Integer.parseInt(st.nextToken());
dp = new int[n + 1][2]; // w, v
// 배열 초기화
dp[0][0] = max;
System.out.println(Arrays.deepToString(dp));
// 배낭 준비
int weight, value;
for (int i = 1; i < n + 1; i++) {
st = new StringTokenizer(br.readLine());
weight = Integer.parseInt(st.nextToken());
value = Integer.parseInt(st.nextToken());
for (int j = i - 1; j >= 0; j--) {
if (weight <= dp[j][0]) {
dp[i][0] = dp[j][0] - weight;
dp[i][1] = dp[j][1] + value;
break;
}
}
result = Math.max(result, dp[i][1]);
}
System.out.println(result);
}
}처음 코드는 다음과 같았다.
입력받은 순서대로 값을 비교해가며 dp 정보를 갱신한다.
처음에는 dp 기준을 입력받은 순서별 가치의 누적합으로 구했기 때문에 2차원 배열을 이용하였다.
문제에서 주어진 테스트 케이스를 실행시키면 다음과 같이 나온다.
4 7
[[7, 0], [0, 0], [0, 0], [0, 0], [0, 0]]
6 13
[[7, 0], [1, 13], [0, 0], [0, 0], [0, 0]]
4 8
[[7, 0], [1, 13], [3, 8], [0, 0], [0, 0]]
3 6
[[7, 0], [1, 13], [3, 8], [0, 14], [0, 0]]
5 12
[[7, 0], [1, 13], [3, 8], [0, 14], [2, 12]]
14예외 처리를 간단하게 하기 위해 인덱스 0번에 입력받은 값들로 초기화 해두었다.
1번째 값부터 순회하며 이전값, 그 이전값 들을 순회한다.
이전 이력들 중에서 현재의 물건을 더할 수 있으면(남은 weight 이 현재의 weight 보다 작으면) 무게를 빼고 가치를 더한다.
다만 이 방법은 순서에 의존한다는 문제가 있다.
현재 weight 이 이전의 이력들 중 하나만 해당되면 무조건 가치를 더했기 때문에,
해당 결과가 원하던 최댓값이 아닐 가능성이 있다.
현재 문제에서는 틀린 답이지만
날짜와 같이 순서가 존재하는 경우 사용하면 될듯하다.
실패2: 중복 저장
dp 를 관리하던 기준이 ‘입력 순서’ 였기 때문에 발생했다고 생각이 들어
입력 순서와 무관하게 무게별 가치누적합으로 관리하도록 변경하였다.
import java.util.*;
import java.io.*;
public class Main {
private static int n;
private static int max;
private static int[] dp;
private static int result;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
max = Integer.parseInt(st.nextToken());
dp = new int[max + 1];
int weight, value;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
weight = Integer.parseInt(st.nextToken());
value = Integer.parseInt(st.nextToken());
for (int w = weight; w <= max; w++) {
dp[w] = Math.max(dp[w], dp[w - weight] + value);
result = Math.max(result, dp[w]);
}
}
System.out.println(result);
}
}해당 코드도 주어진 테스트 케이스로는 성공하지만 제출하면 실패한다.
for 문 안에 있는 for 문을 보면 입력받은 weight 를 기준으로 max 값까지 순회하며 갱신하고 있다.
다만 위의 코드에서는 동일한 물건이 중복적으로 카운트될 수 있다는 문제가 있다.
예를 들어 아래와 같은 테스트 코드를 실행하면 3번째 물건에서 중복이 발생한다.
4 7
5 12
[0, 0, 0, 0, 0, 12, 12, 12]
4 8
[0, 0, 0, 0, 8, 12, 12, 12]
3 10 -> 중복 발생
[0, 0, 0, 10, 10, 12, 20, 20]
6 13
[0, 0, 0, 10, 10, 12, 20, 20]따라서 이와 같은 중복 카운트를 방지하기 위해 dp 를 1차원 배열에서 2차원 배열로 변경하였다.
이전까지의 누적합을 현재 배열이 아닌 이전의 배열에서 가져와, 현재의 물건 정보는 제외하고 판단한다.
성공
import java.util.*;
import java.io.*;
public class Main {
private static int n;
private static int max;
private static int[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
max = Integer.parseInt(st.nextToken());
dp = new int[n + 1][max + 1];
int weight, value;
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
weight = Integer.parseInt(st.nextToken());
value = Integer.parseInt(st.nextToken());
for (int w = 1; w <= max; w++) {
if (w >= weight) {
dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weight] + value);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
System.out.println(dp[n][max]);
}
}