Merge pull request #1387 from virinci/patch-1

mhayter · web-flow · commit efecea86b93a · 2024-11-02T17:59:34.000-04:00
Fix the remainder group size in binary grouping solution of the multiple knapsack problem
diff --git a/src/dynamic_programming/knapsack.md b/src/dynamic_programming/knapsack.md
@@ -116,7 +116,7 @@ Let $A_{i, j}$ denote the $j^{th}$ item split from the $i^{th}$ item. In the tri
 
 The grouping is made more efficient by using binary grouping.
 
-Specifically, $A_{i, j}$ holds $2^j$ individual items ($j\in[0,\lfloor \log_2(k_i+1)\rfloor-1]$).If $k_i + 1$ is not an integer power of $2$, another bundle of size $k_i-2^{\lfloor \log_2(k_i+1)\rfloor-1}$ is used to make up for it.
+Specifically, $A_{i, j}$ holds $2^j$ individual items ($j\in[0,\lfloor \log_2(k_i+1)\rfloor-1]$).If $k_i + 1$ is not an integer power of $2$, another bundle of size $k_i-(2^{\lfloor \log_2(k_i+1)\rfloor}-1)$ is used to make up for it.
 
 Through the above splitting method, it is possible to obtain any sum of $\leq k_i$ items by selecting a few $A_{i, j}$'s. After splitting each item in the described way, it is sufficient to use 0-1 knapsack method to solve the new formulation of the problem.
 
