https://www.acmicpc.net/problem/12865
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다.
www.acmicpc.net
Knapsack 알고리즘을 사용하면 풀리는 문제이다.
최근에 알고리즘 문제 풀이에 취미가 생겨 문제를 열심히 푸는 중인데, Knapsack 알고리즘을 봐도 이해가 안되어
나름 내 방식대로 이해하고 풀다 보니 Knapsack알고리즘과 똑같이 나왔다 ㄷㄷ.
주어진 개수 = n
주어진 무게 = weight
주어진 무게의 가치 = value
Knapsack 알고리즘은 전체 무게가 weight(주어진 무게)를 넘지 않도록 n 번째까지 항목 중에서 얻어진 최고 이익을
저장하여 Dynamic Programing으로 푸는 방식이다.
처음에 이게 무슨말인지 이해가 안되어 이해를 포기하고 그냥 내 생각대로 해보니 Knapsack알고리즘이 나왔는 데,
이 글 또한 그러한 사람들을 위해 작성 또는 내가 다시보려고 작성한 글이다.
문제에 나와있는 무게와 가치
6 13
4 8
3 6
5 12
말고
아래의 가치로 계산해보고 n(주어진 개수)=5 , WEIGHT(주어진 무게의 값)=15 라고 하자
| weight | value |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 5 | 5 |
5*15 로 2차원 배열을 잡는다. 실제로 생성할 땐 dp[n+1][value+1] 로 생성하자 dp[0][0~15]을 써야하기 때문.
또한. 값을 [1][1] 부터 집어넣자.
첫 번째 항목인
weight=1과 value=1을 먼저 계산한다.
weight=1과 주어진 무게의값 WEIGHT(15)까지 계산을 한다
계산은 각 열의 무게와 weight=1을 빼서 0보다 클경우 value를 집어 넣고
만약 작을 경우 그 이전의 값(바로 위의 행)을 집어넣는다. 그 이전의 값이란 것은 두번째 또는 세번째 항목부터 이해가 될 것이다.
현재 weight=1이고 첫 번째 열의 무게는 1이다 1-1>=0 이므로 1을 넣는다.
현재 weight=1이고 두 번째 열의 무게는 2이다 2-1>=0 이므로 1을 넣는다.
이런식으로 첫 번째 항목을 채운다
만약 첫 번째 항목의 weight=5라면 첫 번째 열에서는 1-5 >=0 이 아니므로 0을 넣는 데, 사실 0이라기보단 그 이전의 값(바로 위의 행)인 dp[0][1]값을 넣는 것이다. 두번째 또는 세번째 항목부터 이해가 될 것이다.
(행은 아이템 순번, 열은 무게)
두 번째 항목은 weight=2이고 value=2이다
현재 weight=2이고 첫 번째 열의 무게는 1이다 1-2>=0 이 아니다. 따라서 이 전의 값(바로 위의 행)을 넣어야한다.
이전의 값(바로 위의 행)은 dp[1][1]값인데 이는 즉, dp[n-1][j] 정도로 볼 수 있다.
현재 weight=2이고 두 번째 열의 무게는 2이다 2-2=>0 이므로 첫 번째 항목처럼 2를 넣는다라고 생각할 수 있지만
아니라 이전(바로 위의 행)의 값과 값을 비교해야한다.
이전(바로 위의 행)의 값은 1이고 현재 나의 값은 2이다 2가 더 크므로 2를넣는다.
현재 weight=2이고 세 번째 열의 무게는 3이다 3-2>=0 이고 3-2=1이다. 이제 남은 1의 값을 활용해야 한다.
이전(바로 위의 행)의 열을 사용한다.
3-2=1 이기 때문에 이전 값(바로 위의 행)의 열은 1,1 -> dp[1][1]이다
현재 weight는 2이며, value=2이고 현재 열은 세 번째 열이다. 2, 3 -> dp[2][3]
현재 열은 이전 값(바로 위의 행)의 1번열의 값 + 현재 값 -> dp[2][3] = dp[1][1]+value -> dp[2][3]=1+2=3
dp[2][3]=3이란 것을 알 수 있다.
현재 weight=2일 때 세 번째 열의 무게가 3이라는 것을 알게 되었으면 이제 또 이전의 값(바로 위의 행)과 비교를 해야한다. 바로 위의행 dp[1][3]=1 이고 현재 dp[2][3]은 3이라는 것을 알고 3이 더크므로 3을 완전히 집어 넣는다.
이로써 규칙은
1. 먼저 그 열의 무게와 현재 항목의 무게를 빼고 무게가 0보다 큰지 확인한다.
2. 0보다 작다면 이전의 값(바로 위의 행)값을 넣는다.
3. 0보다 크다면 현재 열의 무게와 현재 항목의 무게를 뺀 값을 더 한다.
더하는데 빼서 나온 값은 그 이전의 값(바로 위의 행에서 뺀 값의 열번째) 와 현재 항목의 가치를 더한다.
4. 값을 더했다면 이전의 값(바로 위의 행)의 값과 비교를 해 더 큰 값을 완전히 집어 넣는다.
이렇게 해서 두번째도 쭉 집어넣는다.
세 번째 항목은 weight=3이고 value=3이다
현재 weight=3이고 첫 번째 열의 무게는 1이다 1-3>=0 이 아니다. 따라서 이 전의 값(바로 위의 행)을 넣어야한다.
이전의 값(바로 위의 행)은 dp[2][1]값이다. 따라서 1을 넣는다
현재 weight=3이고 두 번째 열의 무게는 2이다 2-3>=0 이 아니다. 따라서 이 전의 값(바로 위의 행)을 넣어야한다.
이전의 값(바로 위의 행)은 dp[2][2]값이다. 따라서 2을 넣는다
현재 weight=3이고 세 번째 열의 무게는 3이다 3-3>=0 이다. 따라서 규칙대로 행동한다.
규칙의 3번인 0보다 크기 때문에 현재 열의 무게와 현재 항목의 무게를 뺀값을 더하는 데 3-3=0이다.
그리고 이 0의 값은 그 이전의 값( 바로 위의 행에서 뺀값의 열번째)는 dp[2][0]인데 이는 0이다.(dp[n+1][value+1] 로 잡았고 값을 [1][1]부터 잡았기때문에 0번쨰는 0으로 초기화 해준다.)
어쨋든 dp[2][0] + 현재 항목의 가치 -> dp[2][0]+3 -> 0+3 =3
그리고 규칙의 4번으로 와서 3과 그 이전의 값(바로 위의 행) dp[2][3]의 값과 비교해서 큰 값을 넣어준다. 둘이 값이 3으로 같기 때문에 3을 넣어준다.
현재 weight=4이고 네 번째 열의 무게는 4이다 4-3>=0 이다. 따라서 규칙대로 행동한다
규칙의 3번인 0보다 크기 때문에 현재 열의 무게와 현재 항목의 무게를 뺀값을 더하는 데 4-3=1이다.
그리고 이 1의 값은 그 이전의 값( 바로 위의 행에서 뺀값의 열번째)는 dp[2][1]인데 이는 1이다.
어쨋든 dp[2][1] + 현재 항목의 가치 -> dp[2][1]+3 -> 1+3 =4
그리고 규칙의 4번으로 와서 4와 그 이전의 값(바로 위의 행) dp[2][4]의 값과 비교해서 큰 값을 넣어준다.
dp[2][4]=3이고 현재는 4이기 때문에 4가 더크므로 4를 넣어준다.
이런식으로 하다보면 아래의 값들이 나온다
이게 Knapsack알고리즘인데 이를 알고리즘적으로 풀이하면
dp[i][j] = Math.max(dp[i - 1][j], value[i] + dp[i - 1][j - weight[i]]);
이렇게 된다.
BOJ 12865 평범한 배낭 문제의 최종 소스는 아래와 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
String T;
T = br.readLine();
st = new StringTokenizer(T);
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int weight[] = new int[N + 1];
int value[] = new int[K + 1];
int dp[][] = new int[N + 1][K + 1];
for (int i = 1; i < N + 1; i++) {
T = br.readLine();
st = new StringTokenizer(T);
weight[i] = Integer.parseInt(st.nextToken());
value[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= K; j++) {
if (j - weight[i] >= 0) {
dp[i][j] = Math.max(dp[i - 1][j], value[i] + dp[i - 1][j - weight[i]]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
System.out.println(dp[N][K]);
}
}