#algorithm
#алгоритм
Вопрос:
Это скорее вопрос алгоритма, чем программирования, но он реализован в программировании, поэтому я задаю его здесь.
У меня есть набор заданных объектов с разными известными размерами, и мне нужно определить максимальное количество объектов, которые можно поместить в другой объем известных размеров. Какие алгоритмы существуют для изучения этой проблемы, кроме комбинаторного подхода методом перебора?
Кроме того, если я предполагаю, что они не расположены, сколько из них поместится?
Другой способ взглянуть на это:
- Какой максимальный набор блоков LEGO я могу собрать, чтобы поместить в коробку, и как мне его рассчитать?
- Какой максимальный набор блоков LEGO я могу поместить в коробку, не расставляя их, и как мне его рассчитать?
Комментарии:
1. Что вы подразумеваете под «не упорядоченным»? Если вы буквально бросаете кирпичи по одному в коробку и подсчитываете, сколько раз вы можете это сделать, прежде чем один из них высунется выше вершины, тогда это случайно (или, скорее, это зависит от деталей того, как каждый из них выпадает). Вы не получите один и тот же ответ каждый раз, если попробуете это в реальной жизни.
2. Ты прав, Стив. В этом случае я ожидаю, что если вы повторите эксперимент, как вы описываете, вы получите среднее значение того, сколько из них поместилось, и, зная оптимальную подгонку, вы сможете вычислить среднее случайное раздувание или то, насколько они растут, не будучи упорядоченными.
3. @Steve нет, но, по-видимому, будет нижняя граница? что является своего рода «обратной» проблемой рюкзака, проблема рюкзака является верхней границей
4. @jk.: да, должна быть нижняя граница, поскольку существует набор неотрицательных целых
xчисел, так что некоторое расположениеxблоков, полученное в результате серии выпадений, не подходит. Любой набор целых чисел, ограниченный ниже, имеет наименьший элемент. Конечно, нижняя граница будет выглядеть как худший игрок в Тетрис.
Ответ №1:
Это классическая проблема CS — прочитайте вики-статью о проблеме с рюкзаком.