Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
serega204
Сообщений: n/a
#1

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

24.03.2010, 21:16. Просмотров 533. Ответов 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 (не существует решение)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.03.2010, 21:16
Здравствуйте! Я подобрал для вас темы с ответами на вопрос рюкзак с элементами (C++):

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

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

Задача про рюкзак - C++
Из заданных N предметов выбрать такие, чтобы суммарный вес был менее 30 кг, а стоимость - наибольшей. Напечатать суммарную стоимость. ...

Жадный алгоритм (рюкзак) - C++
слишком медленно, но верно работает программа. Помогите пожалуйста ускорить. (извиняюсь за транслит или что-то похожее на него) ...

Эвристика. Рюкзак Алладина. - C++
Помогите с заданием пожалуйста. Разработать алгоритм и написать программу для задания Алладина: сколько ценных вещей (заданных массе и...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.03.2010, 21:16
Привет! Вот еще темы с ответами:

С++. Дан рюкзак с заданным объемом... - C++
Кто сможет помогите с решением задачи на С++, буду очень благадарен. Задача: Дан рюкзак с заданным объемом и предметы со своим...

Задача о камнях (почти рюкзак) модификация) - C++
из камней весом p1, p2 ... pn набрать вес W если это возможно вывести yes, если не - no, но есть проблемка: в дополнение к задаче дается...

Задача про рюкзак - ускорить работу программы - C++
Вообщем есть алгоритм, который работает правильно за O(N*W), поэтому при больших значениях будет очень долго считать, нужно изменить так,...

Образовать из матрицы 2 массива с положительными элементами и отрицательными элементами по возрастанию - C++
Дана матрица размера N. Образовать из него 2 массива с положительными элементами и отрицательными элементами по возрастанию. Помогите...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru