What algorithm do bitcoin miners use to choose which tx to include in their block? I understand it's in the miner's best interest to receive as many fees as possible for his hopefully-accepted block, hence it should include the most rewarding (fee / size) txs - up to the 1MB limit.

However, what algorithm do the miners use? It seems like a knapsack problem, which is NP-Hard, so I doubt miners actually go for the optimal solution.

Thanks!
No. this is not knapsack problem and no one need to find optimal solution.

Sort your transactions in mempool by two rules: 


subsequent transactions can not be to the left of parent ones
most profitable transactions (fee/size) gravitate to left


and take leftmost transactions from mempool until 1 mb limit