Поиск  Пользователи  Правила  Войти
Форумы "Планета Excel" » Вопросы по Microsoft Excel
Страницы: 1
RSS
Перебор комбинаций с выбором одной наилучшей по условиям
 
#1
14.02.2018 17:58:09
Всем добрый день. Помогите советом в решении небольшой задачи.
Имеем исходный условный отрезок длиной в 100, и два дополнительных отрезка, один 15, второй 12.
Задача: разместить на исходном отрезке малые в любой последовательности, любым сочетанием с повторениями, но так, что бы из всех возможных вариантов иметь наименьший остаток, если есть несколько вариантов размещения, предпочтение отдаётся тому, где число число размещаемых элементов наименьшее. Ответ должен быть один: количество отрезков длиной 15, количество отрезков длиной 12, остаток.
Хотелось бы сделать это с наименьшим количеством дополнительных расчётных ячеек. Если можете подсказать решением с помощью макроса - тоже хорошо.
 
 
 
#2
14.02.2018 19:04:43
Доброе время суток
Цитата
kenigfinn написал:
Помогите советом в решении небольшой задачи.
Пожалуйста.
Успехов.
 
 
 
#3
14.02.2018 19:06:33
Поиск решения
 
 
 
#4
14.02.2018 19:10:25
"поиск решений" в помощь
я не отправляю Вас заняться поиском решений, я предлагаю воспользоваться инструментом Excel, который так и называется "поиск решений"
15х5 + 12х2 = 99
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
 
 
#5
14.02.2018 19:17:00
причем правильно настроенный "поиск решений" реально позволяет посчитать именно 5х15 + 2х12,= 99 - это 7 отрезков, а не 1х15 + 7*12 = 99 - это 8 отрезков
Изменено: Ігор Гончаренко - 14.02.2018 19:18:26
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
 
 
#6
15.02.2018 13:11:34
Андрей VG, Маугли, очень смешно, посмеялся.

Ігор Гончаренко, спасибо, за ответ по-существу. А есть способ реализовать тоже самое но формулами или макросом?
Изменено: kenigfinn - 15.02.2018 13:15:45
 
 
 
#7
15.02.2018 14:24:19
одна из формул:
=ПОИСКПОЗ(RC[2];(100- ЦЕЛОЕ((100-СТРОКА(R[-2]C[-1]:ИНДЕКС(C1;ЦЕЛОЕ(R1C2/R[-1]C)))*R[-1]C)/R[-1]C[1])*R[-1]C[1]-СТРОКА(R[-2]C[-1]:ИНДЕКС(C1;ЦЕЛОЕ(R1C2/R[-1]C)))*R[-1]C)+(ЦЕЛОЕ((100-СТРОКА(R[-2]C[-1]:ИНДЕКС(C1;ЦЕЛОЕ(R1C2/R[-1]C)))*R[-1]C)/R[-1]C[1])+СТРОКА(R[-2]C[-1]:ИНДЕКС(C1;ЦЕЛОЕ(R1C2/R[-1]C))))/1000;)
с сайтом какие-то траблы не могу указать, что это код (возможны смайлики местами вместо комбинаций; символ скобока
формулы лучше посмотреть в файле их там 3
для 1-го отрезка
для 2-го отрезка
для остатка
формулы автоматически выдадут правильные результаты при:
1. полученном общем количестве отрезков до 500 (при 500 и более буден неправильно указан остаток)
2. длины требуемых отрезков должны быть <= длины исходного отрезка

что-то движок сайта остановился((( и файл прицепить нельзя(((  
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
 
 
#8
15.02.2018 14:25:13
Цитата
kenigfinn написал:
А есть способ реализовать тоже самое
По ссылке тоже самое реализовано на языке Python и Pascal. Если же ваша фраза аналогична популярной в прошлом году "Как будет выглядеть код макроса для решения...", то подождите, может кому-нибудь будет интересно написать код на VBA.
 
 
 
#9
15.02.2018 14:40:58
исходные, как у Вас в файле:
В1 - длина исходного отрезка
В2 - длина первого отрезка
С2 - длина второго отрезка

в ячейку Д3 формула для остатка (формула массива, я записал ее в Д3, на эту ячейку будет ссылаться след. формула):
=МИН((100- ЦЕЛОЕ((100-СТРОКА(A1:ИНДЕКС($A:$A;ЦЕЛОЕ($B$1/B2)))*B2)/C2)*C2-СТРОКА(A1:ИНДЕКС($A:$A;ЦЕЛОЕ($B$1/B2)))*B2)+(ЦЕЛОЕ((100-СТРОКА(A1:ИНДЕКС($A:$A;ЦЕЛОЕ($B$1/B2)))*B2)/C2)+СТРОКА(A1:ИНДЕКС($A:$A;ЦЕЛОЕ($B$1/B2))))/1000)

в ячейку В3 формула для количества 1-го из отрезков (формула массива, я записал ее в В3, на эту ячейку будет ссылаться след. формула)
=ПОИСКПОЗ(D3;(100- ЦЕЛОЕ((100-СТРОКА(A1:ИНДЕКС($A:$A;ЦЕЛОЕ($B$1/B2)))*B2)/C2)*C2-СТРОКА(A1:ИНДЕКС($A:$A;ЦЕЛОЕ($B$1/B2)))*B2)+(ЦЕЛОЕ((100-СТРОКА(A1:ИНДЕКС($A:$A;ЦЕЛОЕ($B$1/B2)))*B2)/C2)+СТРОКА(A1:ИНДЕКС($A:$A;ЦЕЛОЕ($B$1/B2))))/1000;)

в ячейку для количества 2-го из отрезков (это можно записать куда угодно, я записал в С3)
=ЦЕЛОЕ((B1-B2*B3)/C2)
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
 
 
#10
15.02.2018 17:07:41
Задача сводится к решению задачи о рюкзаке, легко решается динамическим программированием, можно реализовать на VBA
(для указанных данных можно сделать и полным перебором всех комбинаций)
Есть несколько вопросов:
1. Каков максимальный размер исходного отрезка?
2. Дополнительных отрезков только два или может быть больше?
3. Необходимо ли делать ограничение на кол-во отрезков или их может быть неограниченно?
4. Критерий оптимизации: остаток как можно меньше при этом наименьшее суммарное кол-во дополнительных отрезков?
5. Отрезки всегда целые числа?
Изменено: MCH - 15.02.2018 17:09:15
 
 
 
#11
15.02.2018 17:28:43
MCH
1. Максимальный размер исходного отрезка 100.
2. Дополнительных отрезков только 2 и их длины на самом деле 1,5 и 1,2.
3. Неограниченное количество отрезков.
4. Верно.
5. Нет. Исходный может иметь до 3 знаков после запятой, дополнительные всегда 1,5 и 1,2.
 
 
 
#12
15.02.2018 17:40:02
Вариант в приложении (поиск решения)
 
 
 
#13
15.02.2018 17:56:04
Вариант через UDF с полным перебором
 
 
 
#14
15.02.2018 18:39:14
MCH офигеть!
Изящно!
Спасибо!
 
 
 
#15
15.02.2018 18:45:39
выше я писал об этом
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
 
 
#16
15.02.2018 19:00:11
Ігор Гончаренко и Вам спасибо большое!
 
 
 
#17
16.02.2018 11:01:05
MCH, чувствую, что наглею, но не поможете с вариантом, если маленьких отрезков 4 варианта разной длины: 2,4; 1,2; 0,9; 0,6?
Пытался разобраться сам, но как я понимаю, в таком варианте уже появляются вложенные циклы, а с их пониманием всё плохо.
 
 
 
#18
16.02.2018 12:49:39
Для смеха еще раз Поиск решения..
 
 
 
#19
16.02.2018 13:52:49
а с учетом предпочтения решения с минимальным количеством элементов:
382.4
11.2
10.9
100.67
всего 50 шт. в остатке 0
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
 
 
#20
16.02.2018 14:11:28
Решение динамическим программированием на VBA, можно использовать до 10 различных отрезков (можно сделать и больше), а также ограничивать каждый вид из отрезков
Изменено: MCH - 16.02.2018 14:47:49
 
 
 
#21
16.02.2018 14:45:52
Всем спасибо большое!
 
 
 
#22
16.02.2018 15:09:20
MCH, а возможно это представить в виде UDF, как было первый раз?
Изменено: kenigfinn - 16.02.2018 15:09:36
 
 
 
#23
16.02.2018 16:05:21
UDF
 
 
 
#24
16.02.2018 16:51:50
MCH,Огромное Вам спасибо!
 
 
 
#25
17.02.2018 20:27:45
см. вложение
функции необходим 1 параметр - массив длин. 1 элемент в массиве - это длина заготовки, остальные элементы - длины деталей.
количество деталей - не ограничено
в результатах допускается 0 количество деталей
если данные позволяют подобрать решение без остатка - оно будет найдено довольно быстро, если таких решений нет, функция переберет ВСЕ возможные варианты и вернет тот, в котором при минимальном остатке длина заготовки набирается из минимального количества деталей
Код
Function OptimumCount(LenArr As Range)
  Dim k&(), optk, L() As Single, o() As Single, v, c&, ar, i&, j&, m&, ost
  ar = LenArr.Value: c = UBound(ar, 2) - 1: m = Int(ar(1, 1) / ar(1, c + 1))
  ReDim k(0 To c): ReDim o(0 To c): ReDim L(0 To c): o(0) = ar(1, 1)
  For i = 1 To c
    L(i) = ar(1, i + 1): k(i) = Int(o(i - 1) / L(i)): o(i) = Round(o(i - 1) - k(i) * L(i), 5)
  Next
  i = c - 1: ost = o(0): If o(c) = 0 Then OptimumCount = k: Exit Function
  Do
    If k(i) > 0 Then
      k(i) = k(i) - 1: o(i) = o(i) + L(i)
      For j = i + 1 To c
        k(j) = Int(o(j - 1) / L(j)): o(j) = Round(o(j - 1) - k(j) * L(j), 5)
      Next
      If o(c) < ost Then ost = o(c): optk = k
      If o(c) = 0 Then Exit Do Else i = c - 1
    Else
      Do
        i = i - 1
      Loop Until k(i) > 0 And i > 0
    End If
  Loop Until k(c) = m
  OptimumCount = optk
End Function
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
 
 
#26
18.02.2018 20:35:34
Цитата
Ігор Гончаренко написал:
см. вложение
Игорь, у меня для отрезков 2,4; 1,32; 0,9; 0,67
твой макрос возвращает решение в 52 отрезка: 2,4*37+1,32*0+0,9*5+0,67*10 = 100
мой находит решение в 45 отрезков: 2,4*40+1,32*1+0,9*0+0,67*4 = 100
 
 
 
#27
18.02.2018 21:24:33
десятичные числа....
2.68 / 0.67 = 4
а целая часть от этого деления = 3 ((((((((
Int(2.68 / 0.67) = 3, на остатках я на это нарвался и там у меня Round есть
спасибо, сейчас поправлю
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
 
 
#28
18.02.2018 21:35:52
в строку в цикле, где определяются количества и остатки необходимо дописать Round (как и у остатков)
Код
        k(j) = Int(Round(o(j - 1) / L(j), 5)): o(j) = Round(o(j - 1) - k(j) * L(j), 5)
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
 
 
#29
19.02.2018 00:06:05
т.к. количество каждого вида отрезков не ограничено, то алгоритм с динамическим программированием можно существенно ускорить
 
 
 
Страницы: 1
Наверх