[수업]Freelancer(0-1 Knapsack 변형문제)

Intro..

알고리즘 개념에 Branch-and-Bound(분기한정법) 관련해서 정리한 게시물을 참고할 것.

결국 이 문제에서 트리를 그리는 형태는 Branch-and-Bound(분기한정법) 방법을 사용했기 때문이다.

문제

풀이

이 문제는 0-1 냅색의 영향을 받은 문제이며 정 반대이다.

• 자세한 0-1 냅색관련 이야기는 다른 게시물에 있으니 필요하면 참고
• 왼쪽은 현재 Freelancer 특징 <-> 오른쪽은 기존 0-1 냅색 특징
  • Freelancer <-> 0-1냅색
  • 수입 이상 <-> 무게 이하
  • 시간 최소 <-> 이익 최대

또한, 냅색(Knapsack) 문제 중 Fractional원리도 사용 + 깊이우선(or 우선순위큐)으로 best of.. 사용

• i(=수입), t(=시간), i/t(시간당 수입)
  • i/t 부분이 Fractional 원리가 사용된 부분!
  • i, t는 문제에서 주어지지만 i/t는 직접 구해야한다.
  • 또한, 문제에서 시간당 수입 i/t 가 큰것부터 순서대로 사용하는건 자명하다.
• 위 그림의 예로 문제가 나왔다고 가정을 하며, I(=수입의 한계)는 33으로 주어졌다.

트리의 노드의 구조 : 현재수입, 현재근로시간, I를 넘길수 있는 최소근무시간(이게 중요)

• 또한, 데이터 4개인데 선택시 1, 선택X시 0 이며 각각 왼쪽, 오른쪽으로 그려 나간다.

제일 초기 노드

• 아무것도 선택 안했으니 현재수입=0, 현재근로시간=0 이고 마지막 최소근무시간은??
  • 앞서 얘기했듯이 i/t가 큰것부터 데이터를 선택해 나가야하는건 자명하다.
  • 그럼 4번째 데이터를 우선 볼 수 있고 총 수입이 24이므로 시간 6을 전부 가진다.
  • 이후 i/t가 큰건 3번째 데이터 이므로 이 데이터를 사용하는데 이때 총 수입이 30이다.
  • 따라서 24+30=54로써 주어진 I=33 시간을 훨씬 뛰어넘는다.
  • I=33 시간에 맞춰주는게 중요하다.(그래야 시간이 최소가 될 수 있을테니)
    • 이때 사용하는게 Fractional 원리!!!
    • 주어진 수입인 I=33 에서 기존 얻은 수입인 24를 뺀 수입만큼 시간을 더 가져야한다.
    • 33-24=9 로써 9의 수입이 더 필요하다.
    • 3번째 데이터의 i/t 는 3이므로 시간당 3의 수입을 가진다.
    • 이 말은 3*3=9 인 9 수입을 얻기 위해선 3번째 데이터의 3의 시간을 가져야한다.
    • 따라서 3번째 데이터의 시간 3과 앞서 구한 4번째 데이터의 시간 6을 더한값이
    • 최종 구하려는 최소근무시간 의 값이 되는 것이다.

첫번째로 4번째 데이터를 선택시 트리 구조

• I를 넘지 않고 모든 수입을 가지기 때문에 현재수입=24, 현재근로시간=6, 최소근무시간=9
  • 즉, 4번째 데이터의 모든 수입, 시간을 가지기 가능한 경우 최소근무시간을 다시 계산할 필요X

4번째 데이터 선택X시 트리 구조

• 현재이익=0, 근로시간=0, 최소근무시간=11.5
  • 최소근무시간이 바뀐 이유는 4번째 데이터를 사용하지 않았기 때문!!
  • 4번선택 안하면 남은건 1,2,3번 데이터이다.
  • 다음 순서인 3번 데이터 다 가져오면 30 수입, 근로시간10 사용이다.
    => 남은 수입인 33-30=3을 어디서 가져오나?
  • 그다음 순서(i/t가 큰)인 1번째 데이터에서 가져온다.
  • i/t=2 이므로 2*1.5=3 이익이기 때문에 여기서 가져오면 1.5의 근로시간이 필요하다.
    • 결론 : 최소근무시간 : 10+1.5=11.5

여기서 I이익 넘긴순간 그 최소근무시간은 the best가 된다.(더 내려갈수록 커지는건 자명)

그 다음 the best를 찾는것은 현재 best값보다 작을 때 될 수 있다.

• 따라서 다른것들도 기존 the best보다 큰 값이 나올게 예상되는 경우엔 바로 pass한다.

마지막으로 이 탐색 방식은 다양한 방법으로 가능한데, 해볼때는 우선순위 큐로 할 것!

• 우선순위큐 사용해서 BOUND(i/t를 의미)가 젤 작은 값을 우선해서 큐에서 사용(pop)