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

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

Восстановить пароль Регистрация
 
serega204
Сообщений: n/a
24.03.2010, 21:16     рюкзак с элементами #1
Очень нужна помощь....нужно реализовать алгоритм решения задачи о рюкзаке с названием 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++
C++ Из двух стеков с упорядоченными по возрастанию элементами создать новый стек с упорядоченными элементами, не удаляя исходные стеки
Задача про рюкзак C++
C++ Эвристика. Рюкзак Алладина.
C++ Образовать из матрицы 2 массива с положительными элементами и отрицательными элементами по возрастанию
Задача про рюкзак C++
Задача про рюкзак - ускорить работу программы C++

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

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

Текущее время: 17:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru