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

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

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

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

24.03.2010, 21:16. Просмотров 524. Ответов 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++
Первая строка содержит количество предметов 1≤n≤10^3 и вместимость рюкзака 0≤W≤2⋅10^6. Каждая из следующих n строк задаёт стоимость...

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

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

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

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

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

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

Из двух стеков с упорядоченными по возрастанию элементами создать новый стек с упорядоченными элементами, не удаляя исходные стеки - C++
Из двух стеков равной длины с вещественными числами создать 1 стек с квадратами значений элементов исходных стеков, не удаляя исходные...

Из двух стеков с упорядоченными по возрастанию элементами создать новый стек с упорядоченными элементами, не удаляя исходные стеки - C++
Здравствуйте. Помогите пожалуйста с программой Из двух стеков с упорядоченными по возрастанию элементами создать новый стек с...

вычислите сумму элементов, которая расположена между теми элементами,которые сами расположены между первым и последним отрицательными элементами. - C++
вычислите сумму элементов, которая расположена между теми элементами,которые сами расположены между первым и последним отрицательными...

Из двух стеков с упорядоченными по возрастанию элементами создать новый стек с упорядоченными элементами, не у - C++
Здравствуйте. Помогите пожалуйста с программой Из двух стеков с упорядоченными по возрастанию элементами создать новый стек с...

Вывести на экран два массива, элементами первого являются элементы, меньшие заданного значения, элементами второго - большие заданного значения - C++
Задан массив целых чисел. Вывести на экран два массива, элементами первого являются элементы, меньшие заданного значения, элементами...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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