![]() |
|
![]() ![]() ![]() |
|
3.14zDoS |
|
|||
Новичок Профиль Группа: Участник Сообщений: 3 Регистрация: 11.11.2004 Репутация: нет Всего: нет |
Есть файл(НазваниеПредмета, Вес, Стоимость):
предмет1 1500 200 предмет2 2000 100 предмет3 1500 200 предмет4 2500 100 предмет5 1000 200 предмет6 2500 100 предмет7 1500 200 предмет8 500 100 Как наполнить StringGrid так чтобы не превышалась грузоподъемность(5000) а стоимость была максимальна. Меня интересует метод Монте-Карло. Немогу в него врубится. |
|||
|
||||
podval |
|
|||
![]() Где я? Кто я? ![]() ![]() ![]() ![]() Профиль Группа: Экс. модератор Сообщений: 3094 Регистрация: 25.3.2002 Где: СПб Репутация: 18 Всего: 62 |
Модератор: Эта тема клонирована уже дважды под разными названиями в разных разделах.
В чем все-таки проблема? Отбрасывая всякие упоминания о StringGrid, обратимся к методу Монте-Карло. С какого места непонятно? |
|||
|
||||
podval |
|
|||
![]() Где я? Кто я? ![]() ![]() ![]() ![]() Профиль Группа: Экс. модератор Сообщений: 3094 Регистрация: 25.3.2002 Где: СПб Репутация: 18 Всего: 62 |
Я бы предложил такое направление.
Поскольку все переменные в задаче целочисленные, то и применять надо целочисленные методы. Допустим, обозначим Ci - множество стоимостей, mi - множество масс i-х предметов. Xi - управляемые переменные, принимающие значение 1, если i-й предмет включен в оптимальный план, и 0, если не включен. Имеем целевую функцию:
где M - максимальная общая масса. Выглядит идиотски ![]() О методах решения можно справиться в книге Вагнер. Исследование операций. Т. 2. В основном они все сводятся к частичному перебору вариантов. Кое-что здесь есть в качестве введения: http://optimizer.by.ru/implicits.htm |
|||
|
||||
~FoX~ |
|
|||
![]() НЕ рыжий!!! ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 2819 Регистрация: 8.10.2003 Где: Зеленоград Репутация: 2 Всего: 68 |
3.14zDoS
Полный перебор тебе даст оптимальный вариант/ты Но если это не кртично, то можно посчитать удельную стоимость товара - вес/цена. Отсортировать по убыванию. Взять предмет с самой большой уд.стоимостью и прибавляя к нему следующий товар проверять, что М<5000. Если да, то берем следующи товар, если нет, берем товар следующий за ним. Это будет быстрее, но вероятно что у тебя останеться пустое место (М строго меньше 5000). Добавлено @ 17:18 3.14zDoS Завтра выложу код на паскале если хочешь с решением полным перебором и варианта с удельной стоимостью. "А сейчаз пора спать" ![]() |
|||
|
||||
~FoX~ |
|
|||
![]() НЕ рыжий!!! ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 2819 Регистрация: 8.10.2003 Где: Зеленоград Репутация: 2 Всего: 68 |
3.14zDoS
Вот пример с удельной стоимостью.
Прости, что без коментариев, какие то траблы с кодировкой. Тип TGen заполняется не из файла, но это ты сам допишишь. Я сортил методом пузырька, ты можешь использовать любой другой алгоритм. |
|||
|
||||
~FoX~ |
|
|||
![]() НЕ рыжий!!! ![]() ![]() ![]() ![]() Профиль Группа: Участник Клуба Сообщений: 2819 Регистрация: 8.10.2003 Где: Зеленоград Репутация: 2 Всего: 68 |
Вариант с полным перебором выложу попозже, секйчас работы много.
|
|||
|
||||
![]() ![]() ![]() |
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |