How to select a random element from a list based on its weight?

Question

Algorithms

Good afternoon.
One problem stuck in my head from the social security.
I'll forgive you in advance for not quite precisely formulated conditions, but the essence is something like this:
There is an array of advertisers.

[
{data: {...}, w: 5},
{data: {...}, w: 1000}
{data: {...}, w: 3}
]

Where data is the info that needs to be placed on an advertising banner on your site, and w is the "weight" of this advertiser, roughly speaking the amount he paid.
It is necessary to write an algorithm that will randomly select an advertiser , but the hit frequency should depend on the "weight" - w.
That is, if w = 1000, then the banner should be shown more often than advertisers with smaller w.

Answer 1

Such an approach is possible. It's interesting to read the criticism.

var banners = [];
// Генерируем тестовый массив баннеров
for( var i = 1; i <= 5; i++ ){
  banners.push( {
    data: i,
    w: Math.floor( Math.random() * 1000 ) + 1 // Вес баннера от 1 до 1000 к примеру
  } );
}
console.log(banners);
var wt = 0; // Сумма веса всех баннеров
for( var i = 0; i < banners.length; i++ ){
  var banner = banners[i];
  banner.bound = wt += banner.w; // Определяем границу, которая зависит от веса
}
console.log(banners); // Проверить наглядно какие границы созданы
// Генерируем число от 0 до wt
var r = Math.floor( Math.random() * wt + 1 );
for( var i = 0; i < banners.length; i++ ){
  // Ищем какой баннер попал в полученное случайное число
  var banner = banners[i];
  if( r > banner.bound - banner.w && r < banner.bound ){
    console.log('banner ' + banner.data); // В итоге при таком подходе вероятность выпадения более ценного баннера выше, главное чтоб вес был > 0, иначе баннер найден неправильно.
  }	
}