Алгоритм ранца на время

Question

Я использую VB.NET и пытаюсь придумать какой-нибудь алгоритм, псевдокод или код VB.NET, которые позволят мне сделать следующее (надеюсь, я смогу это хорошо объяснить):

У меня есть 2 коллекционных объекта, Cob1 и Cob2. Эти объекты коллекции хранят объекты, которые реализуют интерфейс, называемый ICob. ICob имеет 3 свойства. Булево свойство IsSelected, свойство Length, которое возвращает TimeSpan, и свойство Rating, представляющее собой короткое целое число.

ОК, теперь в Cob1 хранится около 100 объектов, а Cob2 - пустая коллекция. Я хочу выбрать объекты из Cob1 и скопировать их в Cob2. Я хочу, чтобы при выборе объектов соблюдались следующие правила:

1. Я хочу иметь возможность указать временной интервал, и я хочу, чтобы было выбрано достаточное количество объектов, чтобы соответствовать указанному мною временному интервалу (на основе свойства Length). Так, например, если я передам 10-минутный промежуток времени своей функции, он должен выбрать достаточно объектов, которые заполняют все 10-минутное окно, или приблизиться к заполнению, насколько это возможно.

2. Ни один объект не должен быть выбран дважды.

3. Объекты с более высоким рейтингом (через свойство Rating) должны иметь больше шансов быть выбранными, чем другие объекты.

4. Ни один объект, который был выбран за последние 30 минут, не должен выбираться снова (чтобы каждый объект в конечном итоге был выбран по крайней мере один раз), независимо от рейтинга.

Может кто-нибудь дать мне несколько советов о том, как этого добиться? Советы могут быть в форме умственных процессов, примера кода VB.NET, псевдокода или всего, что может мне помочь.

Спасибо

EDIT:

Возможно, это помогло бы всем, если бы я раскрыл, что я пытаюсь сделать в реальной жизни.

Я пишу программное обеспечение для радиостанции, которое будет автоматически выбирать музыку и рекламу для воспроизведения, вроде компьютерного менеджера программ.

Длина представляет длину звукового байта (либо песни, либо рекламы), и рейтинг - это просто так. Если песня популярна, она получает больше эфирного времени. Если рекламодатель платит больше денег, он также получает больше эфирного времени.

Таким образом, моя программа должна выбирать песни, которые воспроизводятся в течение 20 минут или около того, а затем выбирать рекламные объявления для воспроизведения в течение 5 минут или около того.

Надеюсь, это немного поможет.

Спасибо за вклад от всех!

Alan

Answer 1

Обратите внимание:

Ограничение 1 взято из классической задачи о ранце , которая работает на наборах, как требуется ограничением 2.

Ограничение 3 довольно расплывчато. Лучше иметь более высокую стоимость или более высокий охват продолжительностью жизни? Если вы не задаете целевую функцию для максимизации (или, если быть точным, их две: продолжительность жизни и скорость), то есть некоторые оптимальные по Парето решения.

Ограничение 4 реализуемо, если сделать объект карты -> последний раз выбранным, в виде черного списка.

Короче говоря: сначала я бы отфильтровал набор, занеся в черный список объект по ограничению 4, а затем применил алгоритм ранца.

Answer 2

Для реализации 4. Я полагаю, вам нужно сохранить дату / время, когда Cob был выбран в последний раз. Затем я сделал бы это в следующие шаги:

1. Отфильтруйте те, которые не были выбраны в течение последних 30 минут.

2. Сортировка по рейтингу и установка курсора на первый элемент в списке.

3. Проверьте временную шкалу товара. Если оно достаточно короткое, чтобы поместиться в указанное время, выберите его. Если нет, перейдите к 3 и перейдите к следующему пункту.

4. Проверьте, заполнен ли ваш временной интервал. Если да, то все готово. Если нет, перейдите к 3 и перейдите к следующему пункту.