Hopefully by that point the block size will be bigger. If the block size is bigger, than the problem is just "include every transaction". But yes, the bitcoin r

Hopefully by that point the block size will be bigger. If the block size is bigger, than the problem is just "include every transaction". But yes, the bitcoin rewards will continue halving until sometime in 2110-2140, where they hit zero. At some point, transaction fees will be more important than the block reward. Therefore, to be efficient miners would need to solve the knapsack problem if they wanted to create a maximum value block. However, we are lucky here, the knapsack problems is one of the few NP-complete problems that isn't a total mess to deal with, and can be solved in O(nW) time, where W is the greatest common divisor for the weights and n is the length of the input.