arXiv:2611.15780 · v1

Multiple-Choice Knapsack with Small Items

首次提交 2026-11-12 01:55

版本更新 2026-11-12 01:55

雷达观测 2026-11-13 14:16

摘要

The Multiple-Choice Knapsack problem is a generalization of the Knapsack problem in which items are partitioned into disjoint classes and exactly one item must be selected from each class. Besides the standard dynamic program running in time $\mathcal{O}(nc)$, where $n$ is the total number of items and $c$ is the knapsack capacity, no other pseudopolynomial-time algorithm is currently known. We present an $\mathcal{O}(n+w_{\max}^4)$-time algorithm, where $w_{\max}=\max_i (w_{in_i}-w_{i1})$ is the maximum weight range within a class.

期刊信息：LIPIcs.ESA.2026, 29:1-29:12