Как отмечает @payne в своем комментарии, это действительно то же самое, что и проблема с рюкзаком.Таким образом, решение заключается в простом алгоритме динамического программирования.
Скажем, файлы располагаются один за другим в некотором порядке в списке.Сначала у вас есть выбор: включить первый файл или пропустить его.Если вы решите включить его, доступное пространство уменьшится на размер этого файла.Если вы решите пропустить его, доступное пространство останется неизменным.Теперь вы можете получить второй файл в двух состояниях.В первом вы выбрали первый файл и, таким образом, у вас меньше места, а в другом вы пропустили первый файл и у вас больше места.Для каждого из этих сценариев вы снова можете включить или пропустить второй файл.
Обратите внимание, что вы можете определить свое состояние просто по файлу, который вы рассматриваете в данный момент, и доступному пространству, которое у вас есть.Как только вы перешли последний файл или пробел закончился, вы подошли к концу этой строки выбора.
Это приводит к простому повторению:
min_waste(index,space)={
o if space=0 # no more space available, so 0 wastage
space if index>=size(files) # no more files left, whatever is left is wasted
min_waste(index+1,space) if size(files[index])>space # current file is too large skip ahead
min( min_waste(index+1,space), min_waste(index+1,space-size(files[index])) ) otherwise
# minimum of choosing this one and skipping ahead
}
Вы можетерешите реализовать это, заполнив таблицу (т.е. двумерный массив) снизу вверх, или просто запишите это как рекурсивную функцию и запомните.
Это дает вам минимальные потери, но не какие файлы были выбраны для достиженияЭто.Но вы можете легко изменить его, чтобы сохранить информацию о выборе, который он делает в каждом состоянии, и использовать его для построения последовательности выборов из начального состояния.