Многомерная задача о рюкзаке?

Question

[Михаил]

Есть многомерная задача о рюкзаке
(только танкере)
Требуется составить алгоритм решения.
(и решить)

Как я понял этапов несколько.
1 этап. Усреднение величин ресурсов
2 этап. Опр очередности
3 этап. Опр. максимального числа ресурсов (которые влезут в танкер)

Нужна помощь преобразовать это в понятное решение

Comments

[Akina]

Да в чём проблема-то? какая разница, сколько измерений? всё равно - если нужен глобальный оптимум, то полный перебор, а в каком порядке - неважно.

[Михаил]

Akina, насколько я знаю, есть некоторые методы оптимизации (как минимум отсечение заведомо неоптимальных укладок). Но в целом - если требуется точное решение - то только перебор.

[Akina]

насколько я знаю, есть некоторые методы оптимизации (как минимум отсечение заведомо неоптимальных укладок).

Есть, есть... но вменяемо они работают только в очень частных случаях. И практически все предназначены исключительно для одномерной задачи. Показанные же данные не только двумерны, но и достаточно равномерны - тут Вы скорее потеряете на проверках, чем приобретёте на отсечениях.

[ambisinister One]

Михаил, Строится диаграмма для максимальных значений кубатуры и цены.
В точках пересечения, будут лежать средние значения для всех шестнадцати параметров.
Тут ещё обратная пропорциональность проглядывает во весь рост)

Answer 1

[Griboks]

В задаче отсутствует ограничение по форме объёма, только два максимума. Поэтому её можно решить обычной оптимизацией. Существует очень много различных методов решения, онлайн калькуляторов, а также библиотек для языков программирования.

целевая функция = стоимость → макс.
масса→макс
0<масса<=1000
объём→макс.
0<объём<500

Answer 2

[Rsa97]

Для 16 товаров проще всего сделать прямой перебор. Всего то 2¹⁶ вариантов.

Comments

[Михаил]

Лол

[Михаил]

Хорошая шутка

[Михаил]

Это надо в ручную решать. Без кода

[Rsa97]

Михаил, Ну, успехов тогда. NP-полные задачи решаются либо точно, но полным перебором (возможно, с оптимизацией), либо приближёнными методами, но, естественно, неточно.
Если каждый груз имеется в одном экземпляре, то решения два:
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14) => (1000, 485, 220)
(1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15) => (995, 487, 220)

[Rsa97]

Михаил, Для варианта, когда можно взять несколько одинаковых грузов 5 разных решений с ценой 251.
(0, 0, 0, 0, 0, 8, 0, 0, 0, 4, 0, 0, 0, 1, 0, 0) => (1000, 495, 251)
(0, 0, 0, 0, 0, 9, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0) => (999, 492, 251)
(1, 0, 0, 0, 0, 2, 0, 0, 0, 8, 0, 0, 0, 2, 0, 0) => (1000, 475, 251)
(1, 0, 0, 0, 0, 3, 0, 0, 0, 8, 0, 0, 0, 1, 0, 0) => (999, 472, 251)
(1, 0, 0, 0, 0, 4, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0) => (998, 469, 251)