Новости:

Из правил форума: Тема должна отражать суть вопроса, топики типа "help please" будут удаляться!

Главное меню

Подбор слагаемых под нужную сумму

Автор Exc_fun, 24.10.2014, 10:37

« назад - далее »

Exc_fun

Очень часто в моем компе бывает куча альбомов, которые хочется быстро и максимально экономично записать на двд диск. То есть заполнить диск объемом 4488 Мб как можно плотнее, чтоб отклонение от этой цифры (остающее свободное место) не превышало 1-3 Мб. Я уже пытался выполнить операцию в Экселе с помощью опции "Поиск решения". Но она работает как-то нестабильно, один раз подбирает, в последующие раз нет. Да и при по попытке редактирования параметров все время вылезает ошибка, хотя в удачном подборе стоят вроде аналогичные цифры. В интернете есть утилита для данной цели SizeMe. Она хоть и выполняет задачу за секунду, но погрешность у нее составляет 1% (по умолчанию она не меняется), а это целых 45 Мб (свободного места на записываемом диске). Пока не могу найти универсального решения в Экселе, чтоб меняя каждый раз лишь размеры получать результат с минимальной погрешностью (устроит 4487 Мб). В прилагаемой таблице в колонке В приведены размеры альбомов, в колонках C и D формулы. Видимо, я неправильно проставляю значения в "Поиске решения" (но оно туго поддается редактированию). Тоже самое хотелось бы иметь готовый макрос (кстати, не знаю куда его вписывать). Могу показать и другие таблицы с которыми эксперементировал, но чтоб не было путаницы, прилагаю пока одну. Пожалуйста помогите решить задачу подбора слагаемых для 4488.

Shadowmaker

Была аналогичная задача.
Решал следующим образом:
1. Сортируешь все записи по убыванию размера файла
2. Пишешь формулу, которая тупо складывает размеры верхнего файла с текущим - протягиваешь по столбику - можно назвать этот столбец накопительным итогом
3. В другом столбце простыс ЕСЛИ проверяешь - насколько твой накопительный итог приблизился к нужно цифре.

У меня при таком подходе получался наиболее близкий к ожидаемому итог.

Exc_fun

#2
Shadowmaker, пожалуйста приведите это на прилагаемой мной таблице. Вся проблема как раз в формуле. Я ее правильно написал? Вы пользовались опцией Поиск решения?

Из сети я взял пример пользования функцией Поиск решения, которая как раз решает подобные задачи (см. вложение). Тут, нажав на "Выполнить", получиться число максимально приближенное к 8500000000. Однако, когда я подставляю свои цифры (размеры папок), то получается чушь. Проверьте, подставя размеры из первой таблицы (из моего прошлого поста).

zs

#3
=A1+ЕСЛИ((4487-A1-A2)>0;A2;0)+ЕСЛИ((4487-A1-A2-A3)>0;A3;0)
И так далее, и так для каждой ячейки
С уважением, ZS5

Exc_fun

#4
ZS5, вот эту формулу, объясните, в какую (-ие) ячейку(-и) вписать и как ее привести в действие, чтобы одним кликoм Эксель мне показал (выделил) слагаемые максимально приближенные к 4488 Мб? А с опцией "Поиск решения" вы не пробовали?

zs

показать (выделить) слагаемые одним кликом: ячейка с суммой - опция формулы-влияющие ячейки

Exc_fun

Цитата: zs от 24.10.2014, 19:44
показать (выделить) слагаемые одним кликом: ячейка с суммой - опция формулы-влияющие ячейки

Неправильно. Я ведь просил провести операцию именно с моей таблицей https://forum.msexcel.ru/index.php?action=dlattach;topic=10476.0;attach=14349
а вы дали лишь сухой результат с неба взятыми тремя цифрами. Я так и не понял, какой алгоритм выискивает слагаемые? Вставьте мои 51 цифр так чтобы результат (скажем 6 или 9 слагаемых) высветился в ячейках зеленым цветом.

MCH

Эта задача близка к задачи оптимизации линейного раскроя, самый простой способ - это решать жадным алгоритмом, но не всегда будет найден оптимальный результат.
решал собственным алгоритмом, получились следующие результаты:
=2735,1+452,1+413,7+308,8+162,5+152,3+140+123,5
=1097,1+1047,9+656,2+628,6+579+305,9+173,3
=1075,3+924,1+586,6+277,6+179,9+179,1+153,4+146,6+122,9+114,5+102,9+97,1+91,1+88,6+82,5+82,5+73,4+58,7+51,2
=586+103,1+94,4+73,6+52,7+46,7+43,6+38,4+30,4+30,3+28,5+27,7+27,6+25,9+24,1+17,4

Есть наработки по нахождению слагаемых под нужную сумму: http://www.excelworld.ru/forum/10-5196-1


MCH

"Жадный" алгоритм тоже неплохо справляется на этих данных

Exc_fun

#9
Цитата: MCH от 24.10.2014, 21:24
Эта задача близка к задачи оптимизации линейного раскроя,
[/i]
Мне нужен не сухой результат, а порядок действий в Экселе. А именно, какую формулу и в какую ячейку вписать, чтобы в считанные секунды получить выделенные цветом ячейки - результаты (вариантов с сложением слагаемых для получения 4488 может быть несколько). Я проверил действительно у вас 4 варианта получились четко - 4488. Но как одним кликом получить выделенные ячейки (может сделаете захват экрана и я посомтрю ваш видеоролик)?

Exc_fun

#10
MCH, у вас подборка к трем двд получилaсь отменно. Но мне нужно знать в какую ячейку какую формулу вписать, чтобы все 3 варианта (что получились у вас) выделились разными цветами? И главное, на какую кнопку вы нажимаете, чтоб получить слагаемые? Важно отметить, что каждый файл (точнее его размер) попав в двд1 вторично уже не может быть использован т.к. он уже будет отсуствовать в компьютере после их записи на диск.

MCH

Формулу решения "жадным" алгоритмом я привел выше, каждому файлу присваивается свой номер диска.
Чтобы распределить ровно по 4488 я использовал собственную программу по раскрою, которую делал под заказ (до коммерческой реализации не довел, поэтому файл не выкладываю)
Решение находится нажатием на одну кнопку: https://yadi.sk/i/RqsTOc_ccGMcr

Exc_fun

#12
Если решение одним кликом вы провели собственной программой, которую не хотите нам показать, то, не имея доступа к подобному решению задач, я не смогу этим пользоваться (в будущем). Поэтому данный вариент нахождения слагаемых для меня отпадает. Поэтому рассмотрим второй вариант - посредством опции Поиск решения. Если не затруднит, приведите решение с помощью опции Поиск решения.

MCH

Я не выложил файл не потому, что я жадный, а по тому что оно не совсем подходит как готовое решение.
Пример решения формулами "жадным" алгоритмом я привел в 8 посте.
Если хотите более точно распределять файлы по дискам, то можно адаптировать одно из решений из темы "Подбор слагаемых под нужную сумму": http://www.excelworld.ru/forum/10-5196-1
Подойдет макрос Слэна или динамическое программирование (но оно только для целочисленных данных)
Если будет время, то попробую сделать решение различными вариантами

Exc_fun

#14
MCH, благодарю за старания. Вот тут https://forum.msexcel.ru/index.php?topic=4293.0 случайно не наша тема обсуждается? Там тоже говорят о программе "Раскрой" и чуть ниже программка Optmize. Ее как-то можно адаптировать к моей задаче?
Кстати, вашим "Раскрой"-ем подборка слагаемых была выполнена четко. A это https://www.youtube.com/watch?v=OiiPXEJM2n8 или это https://www.youtube.com/watch?v=S-W_eNsRiZ0 тоже не то? Могу я увидеть вашу программу Раскрой?