I'm reading about Knapsack problem. The approaches to solve that I found:

  • Branch and bound
  • Brute force
  • Dynamic programming
  • Memory functions
  • Greedy

All solutions have exponential time in terms of bits. There is a solution (maybe an approximation algorithm) that solve Knapsack problem with polynomial time in bit terms?

  • 1
    $\begingroup$ No, but you can always invent one, which will prove $P = NP$, so good luck. $\endgroup$ – Evil Jun 15 '16 at 3:56
  • $\begingroup$ @EvilJS No one approximation? Heuristic? $\endgroup$ – eightShirt Jun 15 '16 at 4:02
  • 1
    $\begingroup$ LMGTFY, yes there is FPTAS approximation $\endgroup$ – Evil Jun 15 '16 at 4:07
  • 1
    $\begingroup$ We want you to do a significant amount of research before asking, to see if you can find the answer in standard resources; see, e.g., cs.stackexchange.com/help/how-to-ask. There's little point in us repeating material that's already well described in standard resources. In this case, your question is answered on Wikipedia -- if the answer can be found in the obvious place in Wikipedia (or in any reasonable textbook), you probably haven't done enough research before asking. $\endgroup$ – D.W. Jun 15 '16 at 4:33

Your question is answered in the Wikipedia article on the knapsack problem: https://en.wikipedia.org/wiki/Knapsack_problem#Computational_complexity, https://en.wikipedia.org/wiki/Knapsack_problem#Approximation_algorithms.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.