> The current default Bitcoin implementation makes no effort to solve or even really approximately this problem<p>I think this was somewhat out of date even when it was written. :(<p>When I've sampled it before the solver in Bitcoin reliably produces results which are very close to the best results that an external MILP solver produces... and since a year and a half ago it even considers dependencies in that analysis.<p>The knapsack part of the problem is not that impacting because a block is composed of thousands of transactions, which are mostly very small compared to the block size... and for the lower fee transaction the slope of the fees per unit for the available options is not very high. Basically, so long as you get the high fee transactions it usually doesn't much matter if you fail to eek the last few bytes out of a block.
Many miners require a minimum fee-per-byte for including a transaction in their memory pool of transactions awaiting inclusion in a block. So they would for instance ignore a transaction of B bytes if its fee is less than B * 100 satoshi (at 10^-8 BTC, the smallest unit of account).
Then the miner will often find that its entire memory pool fits inside the 1MB block limit, and the knapsack problem disappears (still leaving the NP-hard conflict resolution problem).