The Markovian property of the problem means that each new basket depends on the changing fruit prices and the currently held basket only.
The real problem in your case, is that you do not know the probability of selecting new fruits to place in the basket. This distribution is changing with time since fruit prices are not constant.
You can use what you have learned to estimate each users current basket. Either you estimate the most probable basket they current have or you can estimate the probability distribution of the basket (i.e., with prob. p1 their basket contents is X1, with prob. p2, X2, etc.).
Next, you need to give some probability distribution to the next state (future basket) given the currently known basket contents. This may be difficult because prices are changing and this distribution is changing with time.
The output of multiplying P(current basket)*P(next basket|current basket) will give you the probability distribution of the user's future basket.
Some more information
Define C[n] the cost of the basket at time 'n'.
Define B[n] the user's basket at time 'n'
And say that given P[n+1] (price list at time 'n') and B[n], you have a set of possible baskets that are based on small changes of B[n] so that the price is P[n+1]. This is S[n+1] -- the belief state at time n+1 (the set of all possible B[n+1] values).
You start with S[0] with is the set of all possible baskets given C[0] the total cost and P[0] the price list at the beginning of the game.
Now you get C[1] and P[1] and for each possible basket in S[0] you determine possible next baskets that fit the given cost C[1] and prices P[1]. The set of all these baskets is S[1].
Now, some possible baskets in S[0] will have several possible following baskets. But some baskets in S[0] will no possible following basket. This is true only if the rules ensure that the user can only make small changes (say change N items for N smaller than the size of the basket). So this is how you eliminate possible baskets from S[0]. Given what you see now, they are no longer possible.
When you continue like this, you will find out that sometimes information given at time 'n' will reduce your belief space not only at time n-1 but also n-2 and may be more.
Essentially, you are looking for sequences of baskets that are possible given the list of P[n] and C[n] from 0..current time. Each of these sequences is equally likely.
Just to summarize, if you substitute your 0 values with some very small value such as 1e-17, your impossible states will still be the furthers apart. As you are trying to derive some sort of ordering of your data, it doesn't matter whether your smallest value is -Inf or -39, as either number will be the smallest value in the dataset.
Best Answer
I am not familiar with what you call mixture Markov models. However, as I say further in this answer, some people call hidden Markov models, dynamical mixture model. It is possible that other people refer to Mixture Markov model then. I would be happy if you could indicate where you have read this term.
The previous answer to this question states things that are somewhat inaccurate about the relationship between mixture models and HMMs. What follows aims at clarifying this.
Mixtures models are simply a weighted sum of probability distributions, nothing more:
$P(X|\theta) = \sum_{i=1}^M w_i p_i(X|\theta_i)$, with $\sum_{i=1}^M w_i = 1$
$M$ is the number of components in the mixture. A random variable can follow a mixture model the same way it follows a probability distribution.
Hidden Markov models (HMM) are far more sophisticated models and mixture models can be a part of these models.
A HMM is based on a Markov Chain of states (said hidden states). It does not model a random variable but a time series (an ordered sequence of values, multidimensional or not). Each state of the Markov chain is associated with a probability distribution that can also be a mixture of distribution (here is the only point where the 2 concepts connect!)
At time $t=0$ a state is drawn from an initial probability mass function. The observation at time $t_0$ is assumed to follow (or to have been generated) by the probability distribution (or mixture depending on the case) associated to this drawn state. At time $t=1$, the system enters a new hidden state that is drawn from a transition matrix and the same procedure is repeated.
Hidden Markov models are sometimes called Dynamical Mixture Models (as in this technical report) because, when states are associated to mixtures of probability distributions, they can somehow be seen as a mixture model that dynamically changes over time. However, these changes are modeled via a transition matrix and are fully part of what a HMM is.
Opposite to what is said in the other answer, an HMM can be without mixture with any number of states (and even an infinite number of states). An HMM with a unique state is basically a mixture model, and if that mixture model has only 1 component, it is a simple probability distribution.