Я разработал алгоритм несколько лет назад, с приложением в Perl и SQL, вы можете прочитать об этом здесь , в комплекте с анализом и проверками, почему он (скорее всего) правильный.
Концепция проста: для каждого элемента выбирайте случайное число, тяните его через какую-то функцию, которая зависит от веса элементов и выбирает элемент с наименьшим значением.
функция:
x[i] = -log(1 - rand())/weight[i]