# Knapsack: there is a polynomial solution in bit terms?

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?

• No, but you can always invent one, which will prove $P = NP$, so good luck. – Evil Jun 15 '16 at 3:56
• @EvilJS No one approximation? Heuristic? – eightShirt Jun 15 '16 at 4:02
• LMGTFY, yes there is FPTAS approximation – Evil Jun 15 '16 at 4:07
• 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. – D.W. Jun 15 '16 at 4:33