21644. The Firm Knapsack Problem (Diamond V)

$1 \le n \le 10^5$개의 물건 각각에 대해 무게와 가격이 주어진다. $i$번째 물건의 무게는 $w_i$, 가격은 $v_i$이다. 무게의 합이 $W$ 이하인 물건들을 골라 가격의 합을 최대화하는 냅색 문제의 최적해(가격의 합)가 $X$일 때, 무게의 합을 $\frac{3}{2}W$ 이내로 하고 가격의 합이 $X$ 이상인 물건의 조합을 아무거나 하나 찾아 출력하시오.

  • 입력 제한: $1 \le n \le 10^5$, $1 \le W \le 10^{12}$, $1 \le w_i, v_i \le 10^6$

풀이 Part 1

먼저 주어진 냅색 문제를 ILP (integer linear programming) 문제로 바꾸면 다음과 같다.

  • 0 또는 1의 값을 갖는 $n$개의 변수 $x_i$를 정의한다. $x_i = 1$이면 $i$번째 물건을 가방에 넣고, $0$이면 가방에 넣지 않는다는 뜻이다.
  • $\sum_{i=1}^{n} {x_i w_i} \le W$일 때 $\sum_{i=1}^{n} {x_i v_i}$를 최대화하는 문제.

당연하지만 냅색도 ILP도 NP-complete이므로 이대로는 풀 수 없다. 하지만 ILP는 근사해를 구하는 간단한 방법이 존재하는데, 그것은 정수 값을 갖는 변수들에 대해 실수 값도 허용하여 LP 문제로 만드는 것이다. 이 경우 각각의 $x_i$는 $0$ 이상 $1$ 이하의 실수 값을 가질 수 있는 문제로 약화된다. 이 과정을 LP relaxation이라고 하며, 기존 문제의 제한을 풀었으므로 기존 문제의 최적해 $X$는 새로운 LP 문제의 최적해보다 작거나 같다. (냅색 문제에서 이렇게 물건의 일부를 가져가는 것을 허용한 것을 fractional knapsack problem이라고도 부른다.)

일반성을 잃지 않고 물건들이 $\frac{v_i}{w_i}$를 기준으로 내림차순 정렬되었다고 가정하면, 이 LP 문제는 아주 간단한 그리디 최적해가 존재한다. 총 무게 $W$가 채워질 때까지 물건 $1, 2, \cdots, k-1$를 순서대로 완전히 넣고, $k$번째 물건을 넣었을 때 무게가 초과되면 그 물건을 일부만 넣는 것이다.

이제 가방이 $\frac{3}{2} W$로 커졌을 때 $k$번째 물건을 완전히 넣을 수 있으면 가격 합이 $X$ 이상인 해를 얻을 수 있음은 어렵지 않게 알 수 있다. $k$번째 물건을 완전히 넣을 수 없다면 어떻게 해야 할까?

풀이 part 2

가방을 $\frac{W}{2}$만큼 키워도 $k$번째 물건을 넣을 수 없다는 것은 $k$번째 물건의 무게가 $\frac{W}{2}$를 초과한다는 뜻이다. 그러면 원래 문제의 최적해에 $k$번째 물건이 있는 경우와 없는 경우로 나누어 생각해 보자.

  1. 원래 최적해에 $k$번째 물건이 있는 경우, $x_k = 1$로 고정하면 새로운 LP relaxation을 얻는다. 원래 최적해에는 $w_i > \frac{W}{2}$인 물건 $i$는 존재하지 않음이 보장되므로, 그러한 $i$에 대해 $x_i = 0$으로 둘 수 있다. 이제 나머지 물건과 남은 공간에 대해 같은 그리디 풀이를 적용하면, 마지막에 잘린 물건의 무게는 항상 $\frac{W}{2}$ 이하이므로 그 물건을 완전히 넣어 원하는 답을 얻는다.
  2. 원래 최적해에 $k$번째 물건이 없는 경우, 단순히 그 물건을 제외한 $n-1$개의 물건에 대한 냅색을 풀어야 한다. 같은 그리디를 적용하면 새로운 $k’$번째 물건에 대해 경우를 나누는 상황으로 돌아오게 된다.

이제 $w_i > \frac{W}{2}$인 물건 $i$를 무거운 물건, 그렇지 않은 물건을 가벼운 물건이라고 하자.

여기서 2)에서 나올 수 있는 최악의 상황을 계속 반복하면 모든 무거운 물건 중 하나를 골라서 넣거나 아무것도 넣지 않는 상황으로 나눠지게 되며, 각각의 상황에 대해 그리디를 한 후 가장 높은 가격을 갖는 경우를 골라서 출력하면 원래 문제의 최적해에 어떤 무거운 물건이 들어가든, 또는 들어가지 않든 간에 항상 가격 $X$ 이상을 갖게 된다. (무거운 물건 $i$가 들어갔다면 무거운 물건 $i$를 넣은 경우의 그리디의 답이 $X$ 이상이고, 무거운 물건이 없다면 무거운 물건 없이 그리디를 한 답이 $X$ 이상이기 때문)

각각의 상황에 대해 그리디를 나이브하게 반복해서 최적해를 얻으려고 하면 $\mathcal{O}(n^2)$ 시간이 걸릴 것이다. 하지만 공통적으로 가벼운 물건들의 집합에 대해 그리디를 하는 것은 동일하므로, 무거운 물건을 무게 순으로 정렬하고 투 포인터를 하거나, 가벼운 물건들을 정렬하고 누적합을 한 후 이분탐색을 하는 방법 등을 써서 $\mathcal{O}(n \log n)$ 이하로 시간을 줄일 수 있다.