0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Have you done any sort of literature review? For example, have you looked at arxiv.org/pdf/1611.07724.pdf? $\endgroup$ Jul 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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.