Knapsack알고리즘

Knapsack알고리즘

---

아래와 같이 n개의 물건과 각 물건i의 무게Wi와 가치Vi가 주어지고 배낭의 용량은 W일때, 배낭에 담을 수 있는 물건의 최대가치를 찾는 문제를 다뤄본다. 

단, 배낭에 담은 물건의 무게 합은 배낭의용량W를 초과하지 말아야 하고, 각 물건은 1개씩만 있다.

 

배낭 문제를 DP로 접근해보자.

변수는 물건, 물건의무게, 물건의가치, 배낭의 용량 총 4가지 이다.

이 중 물건과 물건의 무게는 부분문제를 정의하는데 반드시 필요하다. 

왜냐하면 배낭이 비어있는 상태에서 시작하여 물건을 하나씩 배낭에 담는것과 안담는것을 현재 배낭에 들어있는물건의 가치의 합에 근거하여 결정해야 하기 때문이다. 

또한 물건을 배낭에 담으려고 할 경우 배낭용량의 초과여부를 검사해야 한다.

 

• W : 배낭의 용량
• (vi, wi) : 가치, 무게
• K[i,w] : 물건 1~i까지만 고려하고, (임시)배낭의 용량이 w일때의 최대가치 

i번째 물건을 고려할 때

1. 최적해는 물건 i 를 포함하지 않는다 => 전체 가치는 그 전과 동일하다 (물건1~물건i-1의 가치) : K[i-1,w]
2. 최적해는 물건 i를 포함한다 => 물건i의 가치 + 배낭용량이(w-wi)인경우의 가치 (내가 들어갈 공간을 제외한 배낭의 최대가치) 
3.  

---

위 식을 정리하면

 

i) 현재 이 물건이 가방에 들어올 수 있다 (1번, 2번 둘 중 큰값 선택)

1. 선택한다 -> 물건i의가치+배낭용량(w-wi)인경우의가치
2. 선택안한다 -> 이전 물건까지의 가치

ii) 현재 이 물건이 가방에 들어올 수 없다

1. 이전물건까지의 가치

 

이를 2차원 배열로 나타내면 아래와 같다.

 

 

위 W는 가방의 무게가 0kg일때부터~10kg일때를 나타낸다. 

가방용량이 0일때와 고려 물건이 없을 경우 당연히 가치는 모두 0이다.

i) 고려 물건 1인 경우,

물건1은 무게가 5kg이므로 가방의  용량이 5일때부터 들어올 수 있다.

ii) 고려 물건이 1,2인 경우, (=실제로는  2만 다루고있다)

물건2가 4kg이므로 가방 용량이 4일때부터 들어올 수 있다. 이때  자신이 들어가는게 직전 K[1,4]보다 가치가 크므로 들어간다. 이때, 가방용량이 9가되면 K[1,5]에 10이 더해져 50이된다. (나 자신이 들어갈 공간 빼고도 5kg가 있으므로)

iii) 고려물건이 1,2,3인경우

물건3이 6kg이므로 가방용량 6일때부터 들어갈 수 있지만 30(물건3의 가치)+0(K[2,0] 물건2까지 고려했을때 가방용량0) 보다 40(K[2,6] 물건2까지 고려했을때 가방용량6)이 더 크므로, 같은무게의 직전물건까지의 가치를 가져온다. 그러다 가방용량 10이 되었을 때, 50(직전가치)보다 30(자신의가치)+40(K[2,4])가 더 크므로 70이 된다.

 

이렇게 전에 구해놓은 값을 이용하여 현재 자신의 최적해를 구했기 때문에 마지막 원소가 결국 답이된다. 

 

[입력]

4
10
5 10
4 40
6 30
3 50

 

[출력]
90

[코드구현]

import java.util.Scanner;

public class DP4_KnapsackTest {
 
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int W = sc.nextInt();
		
		int[] weights = new int[N+1];
		int[] profits = new int[N+1];

		int[][] results = new int[N+1][W+1];
		
		for (int i = 1; i <=N; i++) {
			weights[i] = sc.nextInt();
			profits[i] = sc.nextInt();
		}
		int itemWeight = 0, itemBenefit = 0; 
		for (int item = 1; item <= N; item++) {
			itemWeight = weights[item]; // 현 아이템의 무게	
			itemBenefit = profits[item]; // 현 아이템의 가치
			
			for (int weight = 1; weight <= W; weight++) {
				if(itemWeight <= weight){	
					results[item][weight] 
                    = Math.max(results[item-1][weight], itemBenefit+results[item-1][weight-itemWeight]);
				}else{
					results[item][weight] =  results[item-1][weight];
				}
			}
		}
		
		System.out.println(results[N][W]);
		sc.close();
	}

}

 

0-1Knapsack알고리즘을 이용한 문제풀이

https://java-is-happy-things.tistory.com/15?category=1266188 

[Java] SWEA5215_ 햄버거다이어트