PangYeon`s IT Log

https://www.acmicpc.net/problem/12865

Knapsack 알고리즘을 사용하면 풀리는 문제이다.

최근에 알고리즘 문제 풀이에 취미가 생겨 문제를 열심히 푸는 중인데, Knapsack 알고리즘을 봐도 이해가 안되어

나름 내 방식대로 이해하고 풀다 보니 Knapsack알고리즘과 똑같이 나왔다 ㄷㄷ.

주어진 개수 = n

주어진 무게 = weight

주어진 무게의 가치 = value

Knapsack 알고리즘은 전체 무게가 weight(주어진 무게)를 넘지 않도록 n 번째까지 항목 중에서 얻어진 최고 이익을

저장하여 Dynamic Programing으로 푸는 방식이다.

처음에 이게 무슨말인지 이해가 안되어 이해를 포기하고 그냥 내 생각대로 해보니 Knapsack알고리즘이 나왔는 데,

이 글 또한 그러한 사람들을 위해 작성 또는 내가 다시보려고 작성한 글이다.

문제에 나와있는 무게와 가치

6 13

4 8

3 6

5 12

말고

아래의 가치로 계산해보고 n(주어진 개수)=5 , WEIGHT(주어진 무게의 값)=15 라고 하자

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]);
	}
}