High-Utility Itemset mining algorithms are methods for discovering relevant information in a database where items are weighted. Their usefulness has been widely demonstrated in many real world applications. We propose an algorithm to sample itemsets with high average utility under length constraints to avoid the long and rare itemsets with items having low weights.