Knapsack Problem

Knapsack Problem

최대 용량이 W인 가방에 최대 가치의 물건들을 집어 넣는 문제이다.
dp를 이용해 해결할 수 있다.
이전에 해결한 부분 문제가 다음 문제를 해결하는 데 도움이 된다.
f(i, j)가 1~i번째의 물건을 용량 j인 가방에 넣는다고 할 때

1) 최적해에 물건 i 미포함인 경우

f(i, j) = f(i-1, j) 

2) i 포함인 경우는

f(i, j) = Vi (i의 값) + f(i-1, j-Wi (i의 무게))

---

이를 점화식으로 나타내면 다음과 같다.

f(i, j) = MAX( f(i-1, j), Vi + f(i-1, j-Wi) ) (j >= Wi 인 경우)
f(i, j) = f(i-1, j) (j < Wi 인 경우)

자바 코드로 나타내면 다음과 같다.

public class Main
{
    public static int knap(int[] weight, int[] value, int W)
    { // W는 가방 최대 용량
        // k[i][0]와 k[0][i]가 0 이므로 배열 크기 하나씩 크게 만듬
        int[][] k = new int[value.length+1][W+1];
        
        // 가방 용량 0일 경우 
        for (int i=0; i<=value.length; i++)
            k[i][0] = 0;
            
        // 물건 무게가 0일 경우 
        for (int i=0; i<=W; i++)
            k[0][i] = 0;
            
        for (int i=1; i<=value.length; i++)
        { // i는 물건. i가 1일 때 첫번째 물건
            for (int j=1; j<=W; j++)
            { // j는 가방의 임시 용량
                if (weight[i-1] > j)
                // 물건 i의 무게가 임시 가방 용량 초과 시
                    k[i][j] = k[i-1][j];
                else
                    k[i][j] = Math.max(k[i-1][j], value[i-1] + k[i-1][j-weight[i-1]]);
            }
        }
        
        return k[value.length][W];
    }
    
	public static void main(String[] args) 
	{
	    int[] value = {25,15,20,30};
	    int[] weight = {3,1,2,4};
	    int W = 7;
	    // 최대 용량 7인 가방에 물건 최대값 되도록 넣기
		System.out.println(knap(weight, value, W));
	}
}