Variant of 0-1 Knapsack Problem is when you can choose exactly $k$ items from $n$ items, and $k$ is positive integer parameter that came in the input. Is there an algorithm with running time complexity $f(k) \cdot n^{O(1)}$ when $f$ is some function of $k$ only without $n$ that solve the Variant of 0-1 Knapsack Problem? In other words Is there an FPT algorithm for the problem?
2
-
$\begingroup$ Have you done any sort of literature review? For example, have you looked at arxiv.org/pdf/1611.07724.pdf? $\endgroup$– Yuval FilmusJul 7, 2021 at 8:11
-
$\begingroup$ This is a variation of multidimensional 0/1 knapsack that at least hard as 2-d knapsack, so you can't find an algorithm that the running time only depend on $k$, and $n$. $\endgroup$– MR_Jul 7, 2021 at 10:20
Add a comment
|