0-1 Knapsack Problem(배낭 채우기)

문제

어떤 도둑이 배낭을 메고 집에 침입, 도둑은 각 물건의 '무게'와 '값어치'를 알고 있다. 훔칠 물건의 총 무게는 배낭의 용량을 초과할 수 없다.

배낭에 담을 수 있는 최대 값어치를 구해보자

입력

•보석 (item)의 개수: n

•보석 집합 S = {item1, item2,…, itemn}

•wi = itemi의 무게, pi = itemi의 가치

•W = 배낭에 넣을 수 있는 총 무게

목표

maximize 

subject to  and .

여기서 x는 i번째 아이템을 배낭에 넣을 것인지 넣지 않을 것인지에 대한 1, 0 값

    출처 링크 : wikipedia.org

---

Brute-force 방법

- 모든 가능한 경우를 반복하면서 w를 초과하기 않으면서 총 이 익을 최대로 하는 경우를 찾는다.

- 각 물건의 포함/불포함 여부를 하나의 비트로 표현하면 모든 경우의 수는 2n개

탐욕적 방법 1

선택 전략 - 가장 비싼 물건부터 우선적으로 채움

최적의 알고리즘이 아니다!

반례 - ex) W = 30kg

품목	무게	값
item1	25kg	10만원
item2	10kg	9만원
item3	10kg	9만원

 

탐욕적 방법 item_{1 => 25kg => 10만}

최적인 해답 item_{2 +} item_{3 => 20kg => 18만원}

탐욕적 방법 2

선택 전략 - 가장 가벼운 물건부터 우선적으로 채움

최적의 알고리즘이 아니다!

반례 - ex) W = 30kg

품목	무게	값
item1	25kg	20만원
item2	10kg	9만원
item3	10kg	5만원

 

탐욕적 방법  item_{2 +} item_{3 => 20kg => 14만원}

최적인 해답  item_{1 => 25kg => 20만}

탐욕적 방법 3

선택 전략 - 무게당 가치가 가장 높은 물건부터 우선적으로 채움

최적의 알고리즘이 아니다!

반례 -  W = 30 kg

품목	무게	값	값어치
item1	5kg	50만원	10만원/kg
item2	10kg	60만원	6만원/kg
item3	20kg	140만원	7만원/kg

탐욕적 방법  item_{1 +} item_{3 =>25kg => 190만원}

_{최적인 해답}  item_{2 +} item_{3 =>30kg => 200만원}

_{===============================> 더 복잡한 탐욪거 방법을 쓰더라도, 0-1 배낭 채우기 문제는 풀리지 않음}

---

동적 프로그래밍 전략

- V[i][j]를 처음 i번째까지의 item 만으로 무게 j(j <=W)를 넘지 않으면서 얻을 수 있는 최적의 이익으로 정의

– V[i][j] = max(V[i−1][j], vi+ V[i−1][j−wi]), if j ≥ w_i

V[i−1][j], if j < w_i

– when V[0][j] = 0 and V[i][0] = 0

예제 1)

W = 30

Item	Weight	Value
1	5	$5
2	10	$6
3	20	$14

 

	0	5	10	15	20	25	30
0	0	0	0	0	0	0	0
1	0	5	5	5	5	5	5
2	0	5	6	11	11	11	11
3	0	5	6	11	14	19	20

예제 2)

W = 30

Item	Weight	Value
1	2	$12
2	1	$10
3	3	$20
4	2	$15

	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	0	12	12	12	12
2	0	10	12	22	22	22
3	0	10	12	22	30	32
4	0	10	15	25	30	37

코드

 
#include <algorithm>
#include <iostream>
#define N 4
#define W 5
 
using namespace std;
int knapsack(int *w, int* v);
int main()
{
    int w[N + 1] = { 0,2,1,3,2 };
    int v[N + 1] = { 0,12,10,20,15 };
    cout << knapsack(w, v) << endl;
    return 0;
}
int knapsack(int *w, int* v) {
    int V[N + 1][W + 1];
    for (int i = 0; i < N + 1; i++) V[i][0] = 0;
    for (int j = 0; j < W + 1; j++) V[0][j] = 0;
    for (int i = 1; i < N + 1; i++) {
        for (int j = 1; j < W + 1; j++) {
            if (w[i] > j) V[i][j] = V[i - 1][j];
            else V[i][j] = max(V[i - 1][j], V[i - 1][j - w[i]] + v[i]);
        }
    }
    return V[N][W];
}
 

결과

코드에서  max(V[i - 1][j], V[i - 1][j - w[i]] + v[i]) 의 j-w[i]가 중요