рюкзак с элементами - C++

С++ для начинающих

Форум программистов и сисадминов Киберфорум

Войти

Регистрация
Восстановить пароль

serega204

	рюкзак с элементами 24.03.2010, 21:16. Показов 1796. Ответов 0 Метки нет (Все метки) Очень нужна помощь....нужно реализовать алгоритм решения задачи о рюкзаке с названием Meet-In-The-Middle на С++.....вот я псевдокод прикинул а на языке не получается сделать 1. Input: множество натуральных чисел {a1, ... , an} и натуральное число s 2. Output: e[i] принадлежит множеству {0,1}, 1<i<n, такие, что сумма e[i]a[i] = s3. 3. Положить t = n/2 4. Создать таблицу(сумма e[i]a[i] от 1 до t для (e[1],e[2],...,e[n]) которые принадлежат {0,1}) и отсортировать её по первой компоненте 5. для каждого (e[t+1],e[t+2],...,e[n]) которые принадлежат {0,1} 6. do вычислить L = s - сумма(e[i]a[i]), сумма от i = t+1 до n 7. проверить с помощью бинарного поиска, является ли L первой компонентой какой-либо ячейки таблицы 8. if l = сумма (e[i]a[i]) от i=1 до t 9. return (e[i],...e[n]) - решение 10. return (не существует решение)

Programming

Эксперт

39485 / 9562 / 3019

Регистрация: 12.04.2006

Сообщений: 41,671

Блог

24.03.2010, 21:16

Ответы с готовыми решениями:

Рюкзак
Здравствуйте дорогие друзья. Помогите составить задачу про рюкзак, с помощью наивного алгоритма.

Рюкзак
задача в delphi имеются m различных предметов их вес и стоимость. Определить какие предметы можно положить в рюкзак емкостью до 50 кг так,...

И снова рюкзак
Здравствуйте! Пытаюсь решить одну задачу на уже в который день, но никак не получается. На входе два массива объектов: 1....

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

inter-admin

Эксперт

29715 / 6470 / 2152

Регистрация: 06.03.2009

Сообщений: 28,500

Блог

24.03.2010, 21:16

Помогаю со студенческими работами здесь

Сверхвозрастающий рюкзак
Всем привет. Помогите написать программу. Я разобрался в теории, а реализовать не могу. Пусть у нас есть множество предметов...

Greedy - рюкзак
Здраствуйте! Мне по информатике дали проблему рюкзака! Может быть ктото уже слышал про неё. Вот и сама задача: читается n -...

непрерывный рюкзак
Первая строка содержит количество предметов 1≤n≤10^3 и вместимость рюкзака 0≤W≤2⋅10^6. Каждая из следующих n строк задаёт стоимость...

Оптимизировать рюкзак
Доброй ночи, форум! Написал динамическое решение задачи о рюкзаке, но она зависает на весе больше 40 (должна работать при весе <=...

Задача про рюкзак
Всем привет! Есть программа, которая решает задачу про рюкзак. Когда у меня количество "предметов" 5 или 10, то все работает...

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:

Новые блоги и статьи Все статьи Все блоги /
Программный отбор элементов справочника Номенклатура по группе 1С Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор под наименованию группы (на. . .	Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .	Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .	Программный отбор элементов справочника Сотрудники по перечислениям 1С Maks 21.03.2026 Установка программного отбора элементов справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит предопределенное значение перечислений. Процедура. . .
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .

Наверх