배낭 문제
배낭에 넣을 수 있는 최댓값이 정해지고 해당 한도 물건을 넣어 가치의 합이 최대가 되도록 고르는 방법을 찾는 것. → 조합 최적화 문제이며, 냅색 알고리즘이라고도 불림.
냅색 알고리즘은 짐을 쪼갤 수 있는 경우(Fraction Knapsack Problem) 와 쪼갤 수 없는 경우(0/1 Knapsack Problem) 로 나눌 수 있음.
전자의 경우는 Greedy를 사용하며, 후자의 경우는 DP를 사용함.
[백준 12865] 평범한 배낭
문제 접근
냅색 알고리즘이 두 가지로 나뉜다고 했는데 평범한 배낭 문제는 짐을 쪼갤 수 없는 후자에 속함.
dp는 수용가능한 무게를 뜻하고, i는 물품을 뜻함. 가운데에 기록되는 값은 가치가 될 것임.
당연히 0의 무게에서는 어떤 물품도 가지지 못하기 때문에 0으로 기록됨.
dp가 수용할 수 있는 무게가 3이 될 때, 물품 중 무게가 3인 물품을 담을 수 있게 됨.
?) i = 4에서도 가치 6을 기록하는 이유
!) 세로줄의 경우 ~까지 탐색한다는 의미를 가지고 있음.
i = 3에 대해 탐색했는데 6을 담은 상태에서 i = 4를 탐색할텐데 이때, i = 4의 무게는 5이므로 채울 수 없게 됨.
그 대신 i = 3에서 채워진 값을 그대로 가지게 됨. → 누적 탐색이라고 생각하면 편함.
무게 6까지 채우게 되면 다음과 같아질 것임.
참고로 가운데에 기록되는 값은 무게가 dp일 때 가질 수 있는 최대 가치이므로
6이 기록됐던, 8이 기록됐던 상관없이 무게 5에서 최대로 가질 수 있는 가치인 12가 기록되며,
무게 6에서 최대로 가질 수 있는 가치인 13이 기록됨.
하지만 마지막 줄인 무게 7은 기록방식이 달라짐.
이제부터는 두 개 이상의 조합을 통해 값이 구성될 것임.
i = 1은 첫 번째라서 전의 값을 그대로 가져옴.
i = 0일 때의 값은 주어진 배열 범위 밖이기 때문에 0이 되기 때문임.
결국 비교하는 것은 세로 줄 상에서의 전 값(i=0의 값)과 i=1의 무게와 → 0
dp[7 - i=1의 무게]의 값 + dp[i=1의 무게]의 값을 비교하게 된다는 뜻. → dp[1] + dp[6] = 13
그러므로 dp[7] 첫 번째 라인의 값은 13이 됨.
여기에서는 dp[7] 첫 번째 라인 값과 dp[i=2의 무게] + dp[7 - i=2의 무게]의 값을 비교하게 되며,
전자는 13, 후자는 8이 나와서, 전자의 값을 사용하게 됨.
다만 이제부터는 누적된 값(6)이 기록되어 있어 값이 달라짐.
dp[7] 두 번째 라인의 값 13보다 dp[i=3의 무게] + dp[7 - i=3의 무게]의 값 14가 더 커지게 되므로 후자의 값을 사용하게 됨.
dp[7] 세 번째 라인의 값 14가 dp[i=4의 무게] + dp[7 - i=4의 무게]의 값 12보다 더 크게 되므로 마지막 가치는 14로 기록됨.
이런 식으로 dp[7] 네 번째 라인의 값이 결과가 됨.
Top-Down 형식으로 풀게 되면
dp[i][j] = Math.max(backpack(i-1, j) + backpack(i-1, j-w[i]) + v[i]);Bottom-Up 형식으로 풀게 되면
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);같은 식이 나오게 될 것임.
+) Bottom-Up의 경우는 하위 인덱스부터 시작해서 값이 채워지기 때문에 w와 v의 크기를 n+1로 늘려야 함.
코드
[Top-Down]
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
private static int[][] products;
private static Integer[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
products = new int[n][2];
dp = new Integer[n][k+1];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
products[i][0] = Integer.parseInt(st.nextToken());
products[i][1] = Integer.parseInt(st.nextToken());
}
bw.write(backpack(n - 1, k) + "");
br.close();
bw.flush();
bw.close();
}
private static int backpack(int i, int k) {
if (i < 0) return 0;
if (dp[i][k] == null) {
if (products[i][0] > k) dp[i][k] = backpack(i - 1, k);
else dp[i][k] = Math.max(backpack(i - 1, k), backpack(i - 1, k - products[i][0]) + products[i][1]);
}
return dp[i][k];
}
}[Bottom-Up]
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int[][] products = new int[n + 1][2];
int[][] dp = new int[n + 1][k + 1];
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
products[i][0] = Integer.parseInt(st.nextToken());
products[i][1] = Integer.parseInt(st.nextToken());
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
if (products[i][0] > j) dp[i][j] = dp[i - 1][j];
else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - products[i][0]] + products[i][1]);
}
}
bw.write(dp[n][k] + "");
br.close();
bw.flush();
bw.close();
}
}Bottom-Up의 경우, 무게를 더 담을 수 있는지 여부를 조건삼아 반복문으로 구현하기 때문에 dp를 1차원으로 사용하여 불필요한 탐색을 줄일 수 있음.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int[][] products = new int[n + 1][2];
int[] dp = new int[k + 1];
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
products[i][0] = Integer.parseInt(st.nextToken());
products[i][1] = Integer.parseInt(st.nextToken());
}
for (int i = 1; i <= n; i++) {
for (int j = k; j - products[i][0] >= 0; j--) {
dp[j] = Math.max(dp[j], dp[j - products[i][0]] + products[i][1]);
}
}
bw.write(dp[k] + "");
br.close();
bw.flush();
bw.close();
}
}참고 링크
