+ Ответить в теме
Показано с 1 по 1 из 1

Тема: Приближеный алгоритм

  1. #1
    Maria_Z is on a distinguished road
    Регистрация
    28.05.2015
    Сообщений
    2
    Вес репутации
    0

    По умолчанию Приближеный алгоритм

    Есть задача о сумме подмножества и есть приближенный алгоритм ее решения:

    Создаем список S, первоначально состоящий из одного элемента 0.
    Для всех i от 1 до n выполним следующие действия
    Создаем список T, состоящий из xi + y для всех y из S
    Создаем список U, равный объединению T и S
    Сортируем U
    Опустошаем S
    Пусть y – наименьший элемент U
    Внесем y в S
    Для всех элементов zi из U, перебирая их в порядке возрастания выполним:
    Если y + ε*s/n < z ≤ s, положим y = z и внесем z в список S
    (тем самым мы исключаем близкие значения и отбрасываем значения, превосходящие s)
    Если S содержит число между (1− ε)*s и s, говорим Да, в противном случае - Нет

    Само создание списка описано весьма туманно. Возможно ли заполнить список по другой схеме?

    Полный получившийся алгоритм:
    Создаем списки S и Т, первоначально состоящие из одного элемента 0.
    Для всех i от 1 до n выполним следующие действия:
    Записываем в список T xi
    Записываем в список S суммы элемента xi с другими ранее записанными элементами в списке Т
    Создаем список U, равный объединению T и S
    Сортируем элементы из списка U в порядке возрастания
    Отбрасываем из списка U повторяющиеся элементы
    Пусть y – наименьший элемент U
    Внесем y в D
    Для всех элементов zi из U, i от 1 до k, k – длина списка D перебирая их в порядке возрастания выполним:
    Если y + ε*s/k < zi≤ s
    Положим y = zi и внесем z в список D (тем самым мы исключаем близкие значения и отбрасываем значения, превосходящие s)
    Eсли D содержит число между (1− ε)*s и s включительно, говорим Да, в противном случае - Нет

    Насколько критична будет замена?
    Последний раз редактировалось Maria_Z; 28.05.2015 в 09:34.

  2. По умолчанию

     
    Хотите избавиться от рекламы? Зарегистрируйтесь
+ Ответить в теме

Похожие темы

  1. Циклический алгоритм
    Получить значения функции Y=F(x) с использованием цикла(do). F(x)=arctg (х+1/х-1) для х=2.2;2.3;….;3.5(Циклический алгоритм). в Visual Basic ...
    от Дашик) в разделе Решите мне задачку
  2. Алгоритм
    Всех приветсвую, хотелось узнать есть ли какой либо спец. алгоритм ( кроме перебора и сравнения) для нижепоследующей задачи, может кому приходилось...
    от alexey85 в разделе Алгоритмы
  3. Алгоритм Дейкстры, итерационный алгоритм
    Всем привет, помогите пожалуйста кто чем может. Есть задание: пакет, содержащий n программ выполняется однопрограммной ЭВМ. Известна длительность...
    от arogosul в разделе Алгоритмы
  4. Алгоритм комбинаторики
    от Decoder в разделе C и C++

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения