0/1 배낭문제 (Dynamic Programming)

 

결론

0/1 배낭문제 (by DP Alg)

시간복잡도: O(2^n) (비효율적)

또한, 재귀식을 위해 사용한 이중배열이 sparse matrix 형태로써 공간의 낭비도 심하다는 것을 확인할 수 있다.

 

구현은 해보고 넘어가자.

public class KnapSack {
	static int numitem = 3;
	static int weightlimit= 30;
	static int[][] P = new int[numitem+1][weightlimit+1];
	static int[] profit = {0, 50, 60, 140};
	static int[] weight = {0, 5, 10, 20};
	public static void main(String[] args) {
		System.out.println(knapsack(3, 30));
    }
    
	public static int knapsack(int n, int w) {
		int numItem = n;
		int weightLimit = w;
		for (int j=0; j<numItem+1; j++) {
			for (int k=0; k<weightLimit+1; k++) {
				if (k < weight[j]) continue;
				if (j==0 || k==0) { P[j][k] = 0; }
				else {
					P[j][k] = Math.max( profit[j] + P[j-1][k-weight[j]], P[j-1][k]);
					
				}
			}
		}
		return P[numItem][weightLimit];
	}
}

 

Recursive Property를 통해 접근하는 문제는 Recursive Property를 세우기까지가 어렵지만 식을 구하고난 뒤는 1to1 mapping으로 쉽게 구현이 가능하다.

추가로 덧붙인 조건식 2개만 유의하자.

1. if (k < weight[j]) continue:

현재 무게제한 k보다 선택하려는 아이템j의 무게가 더 나간다면 인덱스가 마이너스값이 나오기 때문에 pass하자.

 

2. if (j==0 || k==0) { P[j][k] = 0; }: 

위에서 정의한 P[j][k]에 의해,

P[0][k]: 훔칠 아이템이 없음

P[j][0]: 가방무게제한 0으로써 더 이상 훔칠 수 없음

을 의미하므로 profit은 0이 된다.