온라인 비중이 0-1끼리 엉덩이 문제를 효율적으로 해결하십시오

Question

나는 $ n $ 항목과 크기의 $ b $ 단위를 가지고 있습니다. 각 항목 $ j $ $ w_j $ 단위의 $ B $ 배낭에 넣을 때. 이 항목은 온라인 방식으로 한 번씩 나타납니다. 일단 항목 $ i $ 이 나타납니다, 우리는 그것을 빈 (취소 가능하게)에 배치하거나 무시해야합니다. 목표는 빈에 배치 된 항목의 수를 최대화하는 것입니다. (모든 입력은 양의 정수입니다.)

오프라인 알고리즘은 쉽습니다. $ w_1 \ leq w_2 \ leq \ cdots \ leq w_n $

온라인 패션 에서이 문제를 어떻게 해결할 수 있습니까? 내 접근 방식은 선택 사항을 무작위로 지정하는 것입니다. $ j $ 이 나타납니다. $ p_j $ < / span> 그리고 그렇지 않으면 그것을 무시합니다.

Answer 1

이미 알아 차리거나 적어도 언급하지 않았으므로 문제에 대한 결정적 경쟁 알고리즘이 없음을 알 수 있습니다.(CounterExamples는 두 가지 항목 만 필요하며 알고리즘이 결정적이라는 사실을 사용할 수 있습니다.)

무작위 화를하는 접근 방식은 무작위 화에 의해 극복 될 수 없기 때문에 실제로 무작위 화를하지 않으므로 충분하지 않습니다.그러나 귀하의 문제의 몇 가지 휴식 모델이 있습니다.

일부는 Susanne Albers, Arindam Khan 및 Leon Ladewig가 "임의의 주문 모드의 틈막이 및 갭을위한 향상된 온라인 알고리즘"이라는 Susanne Albers, Arindam Khan 및 Leon Ladewig가 종이에서 찾을 수 있습니다 (1.1 절 참조).