배낭 문제

배낭 문제란 무게와 이익이 있는 물건들을 용량이 정해진 배낭에 넣으려고 할 때 최대의 이익을 얻으려면 어떤 물건들을 넣어야 할까를 결정하는 조합 최적화 문제이다.

배낭 문제는 두가지 유형이 있다.

  • 부분 배낭 문제

    물건을 쪼개서 담을 수 있는 경우 욕심쟁이 방법으로 해결 가능하다.

  • 0-1배낭 문제

    물건을 쪼개서 담을 수 없는 경우 욕심쟁이 방법으로 해결 불가능하다.

배낭 문제 정의

  • n개의 물건 S={object1, object2, …,objectn}
  • 각 물건의 무게 W={w1, w2, …, wn} w는 양의 정수
  • 각 물건의 이익 P={p1, p2, … pn} p는 양의 정수
  • 각 물건이 배낭에 넣어지는 부분 X={x1, x2, …xn} 0<=xi<=1
  • 배낭 용량 M은 양의 정수
  • 배낭 문제의 최적해는 모든 물건 pnxn 합의 최대값, 단 모든 물건 wixi의 합은 M보다 작다(배낭을 찢으면 안됀다.)

해법

단위무게 당 이익이 큰 것부터 먼저 배낭에 집어넣는다. 다 들어갈 때까지 넣다가 안들거나는 무게의 물건을 만나게 되면 이 물건을 남은 공간만큼 쪼개어 담는다.

float frac_ks_GM(int M, int w[], int P[], float X[], int n)
{
  int i;
  float max_profit = 0;
  sort(W, P, n);
  for(i = 1; i <= n; i++) x[i] = 0;
  for(i = 1; i <= n; i++)
  {
    if(W[i] > M) break;
    X[i] = 1;
    M = M - W[i];
  }
  if(i <= n) X[i] = (float) M/W[i];
  for(i = 1; i <= n; i++) max_profit += p[i]* X[i];
  return max_profit;
}

최적 부분 구조

  • 부분 배낭 문제

    최적해인 상태의 배낭에서 임의의 i번째 물건을 z만큼 남겨두고 배낭을 비워 원위치 시키자. 이 상태에서 다시 배낭의 최대 이익을 얻도록 물건을 집어 넣는다면 배낭에서 비워진 물건들이 그 무게 그대로 배낭에 다시 들어가게 된다. 배낭 용량 M과 물건 무게 W={..,wi,..}에 대한 최적해는 배낭 용량 M-z과 물건 무게 W={..,wi-z,…}에 대한 최적해 보다 pi*(z/wi)만큼 더 큼 따라서 최적 부분 구조를 가짐

  • 0-1 배낭 문제

    역시 같은 이유로 최적 부분 구조를 가지지만 최적해는 얻을 수 없다!