Many things are difficult, but that shouldn't be difficult at all: miners just include transactions that pay the most (if space is limited) or that pay minimum X bits, X being defined by the miner, (if the space is not limited). THAT'S IT!
That was implemented years ago and has nothing to do with a floating fee. Miners today can set a min fee amount, a block size, and they order txns by fee and include the top x which will fit.