[알고리즘]Kanpsack(배낭 문제) 알고리즘

Kanpsack 알고리즘

배낭 문제는 다이나믹 프로그래밍에서 가장 유명한 문제이다.

어떤 배낭이 존재하고, 그 배낭 안에 넣을 수 있는 최대 무게가 K라고 하자.
배낭에 넣을 수 있는 N개의 물건이 각각 가치 V, 무게 W를 가지고 있다.
이때 배낭 속의 물건들의 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

배낭문제는 크게
① 물건을 쪼갤 수 있는 배낭문제 (Fraction Knapsack Problem) 와
② 물건을 쪼갤 수 없는 배낭문제 (0/1 Knapsack Problem) 로 나뉜다.

① 의 경우에는 가치가 더 큰 물건을 담고, 남은 무게만큼 물건을 쪼개는 방식으로 그리디(Greedy) 를 이용해 해결할 수 있다.
② 의 경우에는 동적 계획법, 즉 DP(Dynamic Programming) 을 활용해 해결해야한다.

---

알고리즘 진행 과정

*진행 과정을 설명하기 위해 평볌한 배낭 문제의 수치를 이용

가방에 담을 수 있는 물건에 대한 무게와 가치를 표로 나타내면 아래와 같을 때

2차원 배열을 만들고 각 행과 열에 i번째 물건까지 넣을 수 있고, 배낭에 넣을 수 있는 최대무게가 j일 때, 최대 이윤을 저장해나간다.

첫번째 물건과 두번째 물건만을 넣을 수 있을 때의 가방의 무게에 따른 최대 이윤이다

세번째 물건을 넣을 때, DP를 사용하는 이유가 나타난다.
가방의 최대 무게가 7일 때, 세번째 물건을 넣고 나서도 가방의 무게가 4가 남는다.

즉, 가방은 최대 무게가 4일 때와 같은 최대 이윤을 더 남길 수 있는 것이다.

DP[i][j] = V[i] + DP[i-1][j-W[i]]

이후에 마지막 사이클까지 돌고나서의 결과는 아래와 같다.
최대 이윤이 14인 것을 확인할 수 있다.

위의 과정을 통해서 점화식을 나타낸다면 다음과 같다.

각 가방의 가치를 V[n],
각 가방의 무게를 W[n],
최대 이윤을 저장하는 배열을 DP 라고 할 때,

(W[i] <= j) 일 때는
DP[i][j] = Math.max(V[i] + DP[i-1]j - W[i]], DP[i-1][j]

(W[i] > j) 일 때는
DP[i][j] = DP[i-1][j]

---

소스 코드 (java)

import java.util.*;

public class Main {
	static int[] w,v;
    static int[][] dp;
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        
		int n = sc.nextInt();
		int k = sc.nextInt();
        
		w = new int[n+1];
		v = new int[n+1];
		dp = new int[n+1][k+1];
		
		for(int i = 1; i <= n; i++) {
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
		}
		
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= k; j++) {
				if(w[i] <= j)
					dp[i][j] = Math.max(v[i] + dp[i-1][j - w[i]], dp[i-1][j]);
				else
					dp[i][j] = dp[i-1][j];
			}
		}
		System.out.println(dp[n][k]);
	}
}