user63370: 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!

user12983: 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

63370: <p>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.</p>

<p>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.</p>

<p>Thanks!</p>
 12983: <p>No. this is not knapsack problem and no one need to find optimal solution.</p>

<p>Sort your transactions in mempool by two rules: </p>

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

<p>and take leftmost transactions from mempool until 1 mb limit</p>
