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

Задача о рюкзаке, решается ли она жадным алгоритмом? - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
olea
5 / 5 / 1
Регистрация: 30.01.2012
Сообщений: 153
03.11.2013, 01:46     Задача о рюкзаке, решается ли она жадным алгоритмом? #1
Здравствуйте.

Задали сделать задачу о рюкзаке, используя жадину. Даны вес и стоимость предметов. Набить рюкзак предметами, чтобы стоимость была максимальна, а вес не превышал Gmax.

Написала алгоритм, который сортирует данные по цене на единицу веса(стоимость деленная на вес) в убывающем порядке.

После 2-3 проверок, он сдался) Например, максимальный вес - 200. Вот отсортированный массив(первая часть)

ID Ves Tsena
36 33 135
81 200 531
98 141 364
34 152 121

Из нее он выбирает только 36 предмет. Но ведь это неправильно, хотя и стоимость его удельная самая большая.

Как быть? Правильно ли я понимаю, что в случае задачи о рюкзаке жадный метод не оптимален?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.11.2013, 01:46     Задача о рюкзаке, решается ли она жадным алгоритмом?
Посмотрите здесь:

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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gazlan
2861 / 1809 / 272
Регистрация: 27.08.2010
Сообщений: 4,893
Записей в блоге: 1
03.11.2013, 01:54     Задача о рюкзаке, решается ли она жадным алгоритмом? #2
Цитата Сообщение от olea Посмотреть сообщение
жадный метод не оптимален?
...
Кладём в рюкзак первый, а за ним второй предметы. Третий предмет в рюкзак не влезет. Суммарная ценность поместившегося равна 150. Если бы были взяты второй и третий предметы, то суммарная ценность составила бы 190. Видно, что жадный алгоритм не обеспечивает оптимального решения, поэтому относится к приближенным.
Задача о ранце
Yandex
Объявления
03.11.2013, 01:54     Задача о рюкзаке, решается ли она жадным алгоритмом?
Ответ Создать тему
Опции темы

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