What algorithm do bitcoin miners use to choose which tx to include in their block?
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