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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Напишите алгоритм вывода списка ребер неориентированного графа http://www.cyberforum.ru/cpp-beginners/thread995927.html
Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер. Вот начало #include <iostream> using namespace std; int main() { int k,n,i,j; ...
C++ Задача на переполнение Вот такая задачка: Дано число в двоичном виде состоящее из 1млн (короче из огромного количества) символов, нужно это число перевести в десятичный вид. http://www.cyberforum.ru/cpp-beginners/thread995916.html
Указатель на функцию и функциональный класс C++
Есть такой код, но он не компилируется. В коде я использую указатель на функцию "Func", что я делаю неправильно? и как это можно записать в виде функционального класса (в комментариях начал его...
Передача динамического двухмерного массива в функцию C++
Всем добрый вечер. Я понимаю, что эта тема поднималась не раз, но хочу еще раз спросить т.к. конечного решения так нигде и нет. Вот моя программа, которая должна считывать информацию из файла...
C++ Посчитать количество запятых http://www.cyberforum.ru/cpp-beginners/thread995903.html
Во введенной строке заменить все пробелы на запятые, а запятые на точки. Посчитать количество запятых во введенной строке. Нужно написать программу. Заранее спасибо.
C++ Массивы. Обнулить элементы столбцов Здравствуйте! Всю жизнь программировал на Паскале и вдруг си++...помогите пожалуйста с заданием, желательно с объяснением, ибо чайник полный.. Написать программу на языке C++ в среде Microsoft... подробнее

Показать сообщение отдельно
olea
5 / 5 / 1
Регистрация: 30.01.2012
Сообщений: 153

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

03.11.2013, 01:46. Просмотров 1543. Ответов 1
Метки (Все метки)

Здравствуйте.

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

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

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

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

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

Как быть? Правильно ли я понимаю, что в случае задачи о рюкзаке жадный метод не оптимален?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru