ナップサック問題 （knapsack problem）は価値p i p_i p i v i v_i v i n n n 整数計画問題 （Integer programming）のひとつで0-1整数計画問題 という。
Maximize x i ∑ i = 1 n p i x i subject to ∑ i = 1 n v i x i ≤ V {\text{Maximize}}_{x_i} \ \sum^n_{i=1} p_i x_i\\
\text{subject to } \ \sum^n_{i=1} v_i x_i \leq V Maximize x i i = 1 ∑ n p i x i subject to i = 1 ∑ n v i x i ≤ V 貪欲法 ¶ ナップサックの有名な近似解は
サイズあたりの価値p i / v i p_i/v_i p i / v i
品物を1から順にナップザックに詰め込んでいき詰め込めなければストップする
というもの。
Amazon.comにおいて空輸してでも「翌日配送」の表示を出すかどうかのレコメンド問題（Mondal et al, 2022
問題
argmax λ i ∑ E ( Revenue i ) s. t. ∑ i E ( Cost i ) ≤ Budget \text{argmax}_{\lambda_i} \sum E(\text{Revenue}_i)\\
\text{s. t. } \sum_i E(\text{Cost}_i) \leq \text{Budget} argmax λ i ∑ E ( Revenue i ) s. t. i ∑ E ( Cost i ) ≤ Budget λ i ∈ { 0 , 1 } \lambda_i \in \{0, 1\} λ i ∈ { 0 , 1 } i i i
E ( R i ) E(R_i) E ( R i ) i i i
アルゴリズム
利益スコア（benefit score）を計算して、商品をbenefit scoreの降順に並べる
benefit score i = price i ⋅ Δ i weight i ⋅ cost i f l y i \text{benefit score}_i = \frac
{\text{price}_i \cdot \Delta_i}
{\text{weight}_i \cdot \text{cost}^{fly}_i }_i benefit score i = weight i ⋅ cost i f l y price i ⋅ Δ i i 予算内なら順にレコメンド対象にしていく
F L Y : = ∅ , k : = 1 , Budget r e s : = B FLY := \emptyset, k:=1, \text{Budget}^{res} := B F L Y := ∅ , k := 1 , Budget res := B
while ( Budget r e s − d k ⋅ weight k ⋅ cost k f l y ) ≥ 0 (\text{Budget}^{res} - d_k \cdot \text{weight}_k \cdot \text{cost}^{fly}_k ) \geq 0 ( Budget res − d k ⋅ weight k ⋅ cost k f l y ) ≥ 0
F L Y : = F L Y ∪ { product k } FLY := FLY \cup \{ \text{product}_k \} F L Y := F L Y ∪ { product k }
Budget r e s : = Budget r e s − d k ⋅ weight k ⋅ cost k f l y \text{Budget}^{res} := \text{Budget}^{res} - d_k \cdot \text{weight}_k \cdot \text{cost}^{fly}_k Budget res := Budget res − d k ⋅ weight k ⋅ cost k f l y
k : = k + 1 k:=k+1 k := k + 1
end
参考：Mondal, A., Majumder, A., & Chaoji, V. (2022, August). ASPIRE: Air Shipping Recommendation for E-commerce Products via Causal Inference Framework. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 3584-3592).
線形計画問題への近似と貪欲法 ¶ 貪欲法のとき、最初に詰め込めなくなる品物の番号をi ∗ i^* i ∗
x i ∗ = { 1 if i = 1 , ⋯ , i ∗ − 1 1 v i ∗ ( V − ∑ i = 1 i ∗ − 1 v i ) if i = i ∗ 0 if i = i ∗ + 1 , ⋯ , n x^*_i =
\begin{cases}
1 & \text{ if } \ i = 1,\cdots, i^* -1\\
\frac{1}{ v_{i^*} } (V - \sum^{i^* - 1}_{i=1} v_i) & \text{ if }\ i = i^*\\
0 & \text{ if } \ i = i^* + 1,\cdots, n\\
\end{cases} x i ∗ = ⎩ ⎨ ⎧ 1 v i ∗ 1 ( V − ∑ i = 1 i ∗ − 1 v i ) 0 if i = 1 , ⋯ , i ∗ − 1 if i = i ∗ if i = i ∗ + 1 , ⋯ , n とおくと、これはx i ∈ { 0 , 1 } x_i \in \{0, 1\} x i ∈ { 0 , 1 } 0 ≤ x i ≤ 1 0\leq x_i \leq 1 0 ≤ x i ≤ 1
これは整数計画問題であるナップサック問題の実行可能解ではないため、
x i ∗ = { 1 if i = 1 , ⋯ , i ∗ − 1 0 if i = i ∗ , ⋯ , n x^*_i =
\begin{cases}
1 & \text{ if } \ i = 1,\cdots, i^* -1\\
0 & \text{ if } \ i = i^*,\cdots, n\\
\end{cases} x i ∗ = { 1 0 if i = 1 , ⋯ , i ∗ − 1 if i = i ∗ , ⋯ , n とすると、これは貪欲法になる
（※貪欲法は最適解とは限らない）
分岐限定法 ¶ 離散最適化問題の厳密解法。
x i ∈ { 0 , 1 } , i = 1 , ⋯ , n x_i \in \{0, 1\}, i = 1, \cdots, n x i ∈ { 0 , 1 } , i = 1 , ⋯ , n 2 n 2^n 2 n 列挙木 で列挙して解いていく
Mondal, A., Majumder, A., & Chaoji, V. (2022). ASPIRE: Air Shipping Recommendation for E-commerce Products via Causal Inference Framework. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , 3584–3592. 10.1145/3534678.3539197