The user only sets the fee cap but as the median premium is computed based on (FeeCap - BaseFee)/2, they are indirectly setting the gas premium too. Moreover, the fee cap also represents the maximum total (base fee + gas premium) that the transaction sender would be willing to pay.
We are open to both as we don’t want the gas-burning issue to be the main focus of this EIP. This sentence can also be changed. However, we can keep this sentence, and then the miner should also burn x% of gas where x is the average ratio of the base fee to the total fee. If you are interested to know what’s the point of it, have a look at the discussion here. But again, not the main focus here.
The block producer can sort the transaction by the fee cap in the decreasing order and then use a greedy algorithm to include as many transactions as possible. However, to do it much more efficiently by exploiting the fact that the median is so robust, they can also estimate the median from a couple of transactions first. Then include all the transactions where the fee cap is more than this estimated median and start to adjust it by including or excluding transactions from there.
The greedy algorithm is that you just keep adding transactions in the decreasing order of fee cap as long as the median of (FeeCap - BaseFee)/2 is less than the minimum fee cap. However, we can also add the details of the more efficient version in a future write-up if there is enough interest.