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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
olea
5 / 5 / 1
Регистрация: 30.01.2012
Сообщений: 153
#1

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

03.11.2013, 01:46. Просмотров 1480. Ответов 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++
Мне нужно сдать программу на си на задачу о рюкзаке: из n предметов, для которых заданы вес и стоимость, выбрать такие, чтобы суммарный вес...

Задача о рюкзаке - C++
Условие задачи:имеются m предметов с номерами от 0 до m-1, для каждого из которых известна масса и стоимость. Определить какие предметы...

Задача о рюкзаке - C++
И так я все сделал как вы и просили. Условие задачи о рюкзаке: Итак, пусть у нас есть рюкзак объёма W, и список из n вещей, у каждой...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
gazlan
3131 / 1906 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
03.11.2013, 01:54 #2
Цитата Сообщение от olea Посмотреть сообщение
жадный метод не оптимален?
...
Кладём в рюкзак первый, а за ним второй предметы. Третий предмет в рюкзак не влезет. Суммарная ценность поместившегося равна 150. Если бы были взяты второй и третий предметы, то суммарная ценность составила бы 190. Видно, что жадный алгоритм не обеспечивает оптимального решения, поэтому относится к приближенным.
Задача о ранце
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.11.2013, 01:54
Привет! Вот еще темы с ответами:

Задача о рюкзаке - C++
Доброго вечера! Даны n типов предметов, каждый тип обладает своей стоимостью и весом, а также предел грузоподъемности limit. Нужно набрать...

Задача о рюкзаке 0-1 - C++
Здравствуйте! Есть задача о ранце, где даны вес и ценность каждого предмета, а также общая вместимость ранца. Нужно найти максимальную...

не решается задача по параллельному программированию - C++
Всех приветствую. Третью неделю пытаюсь сделать лабу. Не получается решить задачу о спящем парикмахере... Собственно кто может ПОМОЧЬ...

Вычислить нужную комбинацию. Задача о рюкзаке - C++
Добрый день форумчане! Немного завтыкал со сроками сдачи (ну как всегда), и в этот раз не уверен, что успею решить сам. Задача...


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

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

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