[알고리즘] 0-1 배낭 문제 (0-1 Knapsack Problem) - JAVA / 자바

0-1 배낭 문제 (Knapsack Problem)

  : 담을 수 있는 무게의 최댓값이 정해진 배낭에 일정한 가치와 무게가 정해져 있는 짐들을 골라 배낭에 담기는 최대의 가치를 구하는 문제

 

특징

  ① 동적 계획법(다이나믹 프로그래밍, DP : Dynamic Programming)으로 해결할 수 있다.

  ② 다른 버전으로는 물건을 쪼갤 수 있는 Fraction Knapsack Problem이 있다.

---

알고리즘

① 물건의 정보를 표에 저장해둔다
② DP배열을 만든다 (열은 물건 0~i번까지 넣을 수 있음을 의미하고 행은 0~n까지 넣을 수 있음을 의미한다)
  - i, j에서 i번째 물건까지 중에 배낭에 넣을 수 있는지 없는지 판단하여 최적의 방법을 저장한다.
    ㄴ 넣는 것이 최적 = [i - 1][j - i번째 물건 무게] + i번째 물건
    ㄴ 넣지 않는 것이 최적 = [i - 1][j]
    ㄴ 안들어간다 (i번째 물건 무게 > w) = [i - 1][j]

>>> 배낭에 넣을 수 있는 최대의 가치합은 [물건의 개수][배낭의 적재 가능 최대 무게]에 저장된 값이다.

Ex)

물건 정보 \ 물건 번호	1	2	3	4
무게	7	4	2	5
가치	10	2	6	12

>>> 실행 결과 DP 배열

물건 \ 무게	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	10
2	0	0	0	0	2	2	2	10
3	0	0	6	6	6	6	8	10
4	0	0	6	6	6	12	12	18

---

의사 코드 (Pseudo Code)

0-1Knapsack()
	for (i ← 1; i<물건개수; i ← i+1) do {
		for(j ← 1; j<최대무게; j ← j+1) do {
			if(물건[i]의 무게 <= j) do {
				배낭[i][j] ← max(물건[i]의 가치 + 배낭[i-1][j-물건[i]의 무게], 배낭[i-1][j];
			}
			else do {
				배낭[i][j] ← 배낭[i-1][j];
			}
		}
	}
end 0-1Knapsack()

---

Java 코드 구현

public static int knapsack_01() {
	for(int i=1; i<=num; i++)
		for(int j=1; j<=maxW; j++){
			if(weight[i] <= j)
				backpack[i][j] = Math.max(backpack[i-1][j-weight[i]] + cost[i], backpack[i-1][j]);
			else
				backpack[i][j] = backpack[i-1][j];
		}
	return backpack[num][maxW];
}

시간 복잡도

 = O(2^n)