What you can do, to fit it into the classical HMM framework, is define a new hidden state space equal to the product of your current two state space and the output space. Given five possible outputs, this will result in a state space with 10 states. Let us define $S_t$ as the state at time $t$ and $O_t$ as the output at time $t$, which I'll assume can take on values $1, 2, \dots, 5$ for simplicity. $S_t = 1$ might correspond to your original state 1 and $O_{t-1} = 1$, $S_t=2$ to original state 1 and $O_{t-1}=2$, and so forth.
Transition probabilities - The transitions between states $S_t$ and $S_{t+1}$ are very limited once you've seen the output at time $t$, as there are only two states in the state space which it is possible to transition into. You can retain the simplicity of your current transition matrix by making the assumption that the transition probability from $S_t$ to $S_{t+1}$ depends solely on the "part" of $S_t$ that is due to your original definition of state. If you make this assumption, which seems to be what you want to do, you will only have two transition probabilities to estimate, and consequently will not suffer from an explosion of the number of transition probabilities in your model.
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.
Best Answer
According to this Wikipedia article, there are many inference benefits you gain from a HMM. The first inference is the ability to assign a probability to any observation sequence $\mathbf{Y} = (Y_1,\ldots, Y_N)$ by marginalizing over the set of all possible hidden state sequences $\mathbf{X} = (X_1,\ldots, X_N)$:
$P(\mathbf{Y}) = \sum_{\mathbf{X}} P(\mathbf{X}) P( \mathbf{Y} \vert \mathbf{X} )$
This way, you can assign probabilities to observation sequences even in an on-line manner as observations arrive (using the very efficient forward algorithm). An anomaly is an observation that is (relatively) highly unlikely according $P(\mathbf{Y})$ (a threshold can be used to decide). Of course, the value of $P(\mathbf{Y})$ grows smaller and smaller as $N$ increases. Many methods can be used to renormalize $P(\mathbf{Y})$ to keep it within the representable range of floating-point data types and enable meaningful thresholding. For example, we might use the following as an anomaly measure:
$\mathbb{A}_{N} = \log P(Y_N \vert Y_1,\ldots, Y_{N-1}) = \log \frac{P(Y_1,\ldots, Y_N)}{P(Y_1,\ldots, Y_{N-1})}$ $\mathbb{A}_{N} = \log P(Y_1,\ldots, Y_N) - \log P(Y_1,\ldots, Y_{N-1})$