I'm reading about Knapsack problem. The approaches to solve that I found:
- Branch and bound
- Brute force
- Dynamic programming
- Memory functions
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?