Given the following table of sequences, I'm trying to find the smallest set with probability $p = 0.9$.
\
The smallest set consists of some sequences from the table, which probability (column 3) should add up to $p$, while the length (found in the second column) is being minimized.
I'm struggling to find a good approach to find the smallest set, without just trying a lot of options and checking their length. Therefore I was wondering if there exists a fast approach to find the smallest set, given such a table.
The smallest set should be (obviously?) formed by picking the most probable sequences.
For that, you should add to your sheet that column (probability of each sequence). In this case, because $p>0.5$, it should be clear that the most probable sequences are in the last rows (greater $k$, greater probability).
Hence you should acummulate the (total) probability of those sequences, until you get your total desired probability.