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?

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


Your Answer

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