0-1 배낭문제 (도둑놈 짐싸기 문제)

배낭문제는 도둑놈 털어가기 알고리즘과 같다.

배낭이 20Kg짜리를 가져갔는데 이게 왠걸 방에 뭐 비싸보이는게 덕지덕지 있다. 다만 무게와 가치를 잘 따져서 가져가야하는데, 보통은 무게대비 가치가 많은걸 가져가면 되겠지만 만약 이게 100Kg 짜리 다이아몬드라면 잘라서 가져가지는 못하므로 포기한다. 고속터미널에서 파는 싸구려 가방이라 20Kg가 넘으면 찢어진다고 가정하다.

한번 이렇게 있다고 생각해보자.

부피 : 4 5 12 4 100 2

가치 : 7 10 2 4 100 6

문제는 뭔가 비싸보이는것부터 넣어도 안되고 무게대비 비싼걸을 넣어서도 별로 답이 되지 않는다는 것이다.

이럴때는 나머지 공간에 물건들을 싸서 얻을 수 있는 최대의 가치를 리턴하는 함수를 설계한다.

물건을 가져가지 않는경우는 다음과 같다.

최대가치1 = (getMaximum(남은용량, Item인덱스 + 1))

가져가는 경우는 다음과 같다

최대가치2 = ( getMaximum( 남은용량 - Item무게[i], item인덱스 + 1) + Item의가치[i] )

즉 둘중에 큰걸 선택하면 되는것이다.

MAX(최대가치1, 최대가치2)

이제 한번 코딩을 해보면 된다.

public static int getMaximumValue(int capacity, int i)

위 시그니처로 작성해본다.  capacity는 남은 공간, i는 좌르륵 널어놓은 물건의 번호이다.

 public static int getMaximumValue(int capacity, int i) {

  if (i == N)
   return 0; // 물건개수 도달하면 리턴한다.

  int noPick = getMaximumValue(capacity, i + 1);
  int yesPick = 0;
  if (capacity >= weight[i]) { //가방에 여유 공간이 남아있으면
   yesPick = (getMaximumValue(capacity - weight[i], i + 1)) + value[i];
  }

  return Math.max(noPick, yesPick);

 }

코드는 간단하다. 물건을 좌르륵 늘어놓았을때 마지막 물건에 도달하면 리턴.

그리고 픽을 하지않을 경우는 남은 공간을 그대로 함수에 넘겨주고 물건의 번호만 한개 더해준다.

만약 픽미픽미픽미업을 할 경우 일단은 가방에 여유공간이 남아있는거 먼저 체크하고 현재 여유공간에서 물건의 무게를 빼고 리턴할 maximumValue에서 value[i]를 더한다.

이제 yesPick 과 noPick을 비교해서 더 큰걸 리턴한다.

그럼 결과는 잘 나올것이다.

전체코드는 아래와 같다.

package algo;

public class Pack {

 static int[] weight = { 4, 5, 12, 4, 100, 2 };
 static int[] value = { 7, 10, 2, 4, 100, 6 };
 static int N = 6;

 public static void main(String[] args) {

  int result = getMaximumValue(20, 0);
  System.out.println(result);
 }

 public static int getMaximumValue(int capacity, int i) {

  if (i == N)
   return 0; // 늘어놓은 물건개수에 도달하면 리턴한다.

  int noPick = getMaximumValue(capacity, i + 1);
  int yesPick = 0;
  if (capacity >= weight[i]) { //가방에 여유 공간이 남아있으면
   yesPick = (getMaximumValue(capacity - weight[i], i + 1)) + value[i];
  }

  return Math.max(noPick, yesPick);

 }
}

졸면서해서 만약 오류가 있으면 리플을 달아주면 감사하겠습니다.