Доброго времени суток! Помогите пожалуйста решить упрощённую задачу о рюкзаке. Есть 139 единиц груза массой (количество единиц может быть увеличено до 150) от 5.49 до 9.9 тонн, которое надо оптимально загрузить в два вида контейнеров - 27 тонные и 20 тонные(количество контейнеров неограниченно). Объём груза не учитывается, но в 27 тонный контейнер можно загрузить 3 единицы груза, а в 20 тонный - 2 единицы груза. Оптимальным будет считаться решение, при котором будет использоваться наименьшее число контейнеров. В прикрепленном файле вы можете увидеть вводные данные и желаемый результат.
Изначально писал на питоне алгоритм, который брал бы самое большое значение, прибавлял к нему самое маленькое и подбирал наибольшее, которое в сумме давало бы около 27, но понял, что это - неоптимальный вариант.
Доброе время суток. Игорь Нехороших, подскажите пожалуйста, на основании чего вами было сделано заключение, что ваша задача - это упрощённая задача о рюкзаке?
Андрей VG, здравствуйте. На основании того, что здесь нет такой переменной как ценность. Возможно, я ошибаюсь, т.к. к программированию имею лишь косвенное отношение. Буду благодарен, если поправите меня.
Игорь, если жадненьким алгоритмом, то можно и в 54 штуки уместить. 23 двадцати тонных и 31 двадцати семи тонных. Хотя соглашусь - к решению упрощённому рюкзаком это имеет слабое отношение.
чтобы так же... учиться нужно будет лет тридцать (понятно что речь не об этой конкретной задаче, тут достаточно получить код, подготовить данные и научиться нажимать кнопку запуска макроса)
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
Использовал свои алгоритмы для задачи линейного раскроя/упаковки в контейнеры, отсюда: http://www.excelworld.ru/forum/3-21304-1 Плюс немного ручной работы. Даже получилось найти решение в 48 контейнера: 43*27 + 5*20 Раскладка во вложении
PS: получить решение в 49 контейнеров для этого набора данных не сложно, значительно труднее найти решение в 48 контейноеров
Попробовал формульное решение. Нашёл решение 48 контейнеров. Хотя пришлось немного вручную поработать. Решение зависит от последовательности исходных данных, так как формула заполняет контейнеры последовательно и каждый следующий зависит от уже заполненных. Первая формула выбирает тройки, но очень долго считает. Вторая подбирает второй и третий к выбранному грузу. Выбирать первый пробовал разными способами. В прямом порядке, обратном, ближайшие значения к среднему и медиане, а также к максимальному, минимальному, среднему и медиане среди нераспределённых. Стабильного эффекта не даёт. Прикинул, сколько теоретически может быть 20 и 27 тонных контейнеров, чтобы всё разместить. Получилось как у MCH.Вручную задал первые 5 контейнеров на 20 тонн, а потом вручную выбирал комбинацию грузов в первом контейнере на 27 тонн, пока не получил оптимальный вариант полных раскладок.