Мы продаем витую пару, в бабинах по 30 метров и по 70 метров, бабины не разрезаются, продаются целиком. Имеем на складе какое-то произвольное количество тех и других бабин.

Приходит клиент и просит какую-либо длину, произвольную, допустим 150 метров, необходимо написать процедуру которая одним-двумя запросами подберет необходимое количество бабин как можно ближе к этой длине с учетом товаров на складе.

Какие есть решения на запросе?

(0) На запросе думаю, что никаких.
Да и незачем.

(1) То есть остается просто циклический перебор? Не фонтан.

Задача рюкзака плохо решается через операции над множествами :) Да и нафиг это не надо.

почему решение должно использовать в качестве основного объект запрос ?

раскройте понятие "как можно ближе к этой длине"

(3) это не рюкзак, это максиминная задача. (0) гугли симплекс-метод.

(5) клиент может попросить любую длину, нужно из бобин набрать длину не менее этой, а если идет превышение длины то минимальное

Что лучше?
Три куска проволки 70+70+30=170
Или 5 кусков 30х5=150

совместные слау можно решать рекурсивными запросами.

(8) 150 дельта равна 0 это оптимум, если конечно в остатках они есть

вот тема оптимизаций расчетов  с помощью запросов 1с

http://infostart.ru/public/271270/

(6) C чего бы вдруг? Симплекс-метод не нужен, т.к. либо не хватит, либо получится точная длина.

(13) Длина должна быть точная или если невозможно то большая, но с минимумом большинства

(13) с чего ты взял?

Нам нужно оптимальное решение задачи
30*х1 + 70*х2 - ДлинаЗаказ >=0
Х1>=0
Х2>=0

+ ограничение на переменные по остаткам.

Нам нужно получить минимальное отклонение от заказа. Не факт, что будет равно.

(13) Другое дело, что это ранец всего с двумя переменными:
70*X1+30*X2>=А
0<=X1<=B1 (сколько есть на складе), целое
0<=X2<=B2 (сколько есть на складе), целое
70*X1+30*X2 -> MIN
Т.е полный перебор будет порядка B1*B2, но, наверняка можно сократить.

(16) а если типов катушек будет 3 или 4 или 5?

(15) Если снять условие целочисленности переменных, то в пространстве (X1, X2) получим прямоугольник и полуплоскость. Либо они НЕ пересекаются, и тогда бобин не хватает, либо пересекает стороны прямоугольника.

(18) без условия целочисленности жить было бы намного проще математикам, да. Это совсем другая задача.

(14) надо брать не минимум, а убедить клиента, что 170м ему взять лучше, чем 150.

(16) Перебором двумя циклами это понятно, и берем минимум дельты, а вот запросом ?

(17) Перебор может быть больше. Это задача о ранце (или ее модификация). Поищите методы решения - она довольно сильно изъезжена.

(19) "(3) это не рюкзак, это максиминная задача. (0) гугли симплекс-метод." - симплекс метод либо крякнет, что нет решения, либо сядет на равенство. Да и не нужен он в задаче с 1 неравенством (кроме двусторонних ограничений вида 0<=Xi<=Bi).

(23) он не может крякнуть по определению :)

И именно в подобных задачах он решает. Например, задача раскроя, закупки и прочее.

(21) Ты чего так к запросу прицепился? Можно и запросом, скорее всего, но это будет дичайший изврат. И точно не быстрее.

(25) У тебя предложение не перебор двумя циклами?

(26) я тебе в (6) уже написал.

(24) Если бобин не хватает - крякнет. Например, есть бобина 70 м и бобина 30. Требуется, скажем 120 (больше 100).
Какое решение выдаст симплекс-метод (если нет никакого)?
"И именно в подобных задачах он решает. Например, задача раскроя, закупки и прочее." - посмотрите работу Канторовича о раскрое фанеры (за которую он получил Нобелевку. Симплекс-метод появился позже).

(27) Никак не разберусь

(28) Хех, отсутствие решения - это тоже решение :)

А то, что симплекс появился позже, - это разве минус?0_о

(29) Плохо. Делай перебором. А я как-нибудь потом займусь реализацией симплекс метода в общем виде на 1С, давно хотел, спасибо, что напомнил :)

(30) О! Как появится тут студентус с просьбой какой-нибудь базы, подкинь ему эту задачу. Первый полезный диплом по 1С появится!

(0) При 2 размерах тебе и думать не о чем. Разбей на 10-метровые диапазоны от 60 до 210 метров (потом всё повторяется) и выдавай заранее рассчитанные оптимальные наборы.

Но про витуху автор лукавит. 305 м - основной размер, меньше 100 не надо, т.к. стыки портят сигнал, а 100 м - макс. размер из стандарта.
Шифруемся?

(0) запросом выбираешь, сколько есть всяких разных видов бабин, длина которых <=длины, которую клиент хочет. Дальше код почитай что партионное списание, только без цикла особенно, ибо там арифметика и деление по модулю

(33) Так бобины не режем, а целиком отдаем, при чем тут партионка? Нужно либо точно либо избыток минимум

(34) блин, всё разжевывать надо...
в данном случае резать надо не бобины, а длину, которую клиент хочет. При переборе запроса тупыми %,/ и - набираем из доступных остатков максимальное количество самых длинных бобин. Отнимаем их совокупную длину от длины, которую надо намерить, с остатком делаем то же самое, только сместив выборку на следующую строку.

Как вариант можно не просто выбрать все, которые <= нужной длины, но добавить еще одну, которая больше нужной длины. Это тупое соединение с минимумом. И потом посмотреть, что выгоднее - взять одну более длинную ил набирать из коротких

(35) Ты теряешь оптимальность с таким алгоритмом. Лучше уж тупым перебором.

(36) чой-та теряю? Если исходить из того, что чем больше метров в бухте, тем дешевле один метр в ней, то не вижу потерь. А, если вчера были большие но по 5, а сегодня мелки, но по 7, то какой тут в пень запрос может быть?

(0) Надо 10. Что лучше, 2 по 6 или 1 на 20?

(33) То есть если надо 10, а на складе только 20, то все, жизнь не удалась?

(37) условия на стоимость не было. Это уже совсем другая задача. Но то же самое линейное программирование будет.

А теряешь ты на простом примере. Надо 160, бухты по 70 и 30. По твоему алгоритму будет 70+70+30=170. Симплекс же даст 1*70+3*30=160.

(38) В задаче же ясно сказано, что нужно минимальное отклонение. Значит, два по 6 будет оптимальнее 1 на 20.

(40) Симплекс это интересно, напиши уравнения.

На самом деле, у вас задача на поиск минимума функции на дискретном многомерном множестве.
То есть каждая "координата" - это имеющийся на складе вид мотка кабеля (и задана она от 0 до количества мотков на складе).
Значение функции - искомая длина.
Не забываем, также, что функция у нас линейная.
Y=Sum(Li*Ki)
Задаёт в нашем пространстве плоскость.
Нужная длина - это другая плоскость - Y=Const
Их пересечение будет прямая линия.
Соответственно - нас интересует ближайшая к этой прямой линии точка, имеющая все координаты - целые числа.
Также не забываем, что у нас "положительный" кусок системы координат.
То есть наиболее удачным решением будет "прогулка" вдоль прямой в рамках целых координат и вычисление минимума значения.

(0) Моя цена 2000 р :)

(42) в (15) написал. Важнее сам алгоритм решения.

(44) Это не оптимально...

имхо тут не надо сильно оптимизировать, а тупо впаривать самые больших бухты

(47) М, или самые маленькие?

(0) Если задача, только по данным бобинам, а не универсальная, то можно в запросе просто напросто объединением получить вообще все возможные варианты и отсортировать по превышающему остатку, думаю на таких небольших количествах сервер легко пережует данные.

(49) Примерно так

ВЫБРАТЬ 1 КАК Количество Поместить Количества ОБЪЕДИНИТЬ ВСЕ
ВЫБРАТЬ 2 КАК Количество ОБЪЕДИНИТЬ ВСЕ
ВЫБРАТЬ 3 КАК Количество ОБЪЕДИНИТЬ ВСЕ
ВЫБРАТЬ 4 КАК Количество ОБЪЕДИНИТЬ ВСЕ
ВЫБРАТЬ 5 КАК Количество ОБЪЕДИНИТЬ ВСЕ
ВЫБРАТЬ 6 КАК Количество ОБЪЕДИНИТЬ ВСЕ
ВЫБРАТЬ 7 КАК Количество ОБЪЕДИНИТЬ ВСЕ
ВЫБРАТЬ 8 КАК Количество ОБЪЕДИНИТЬ ВСЕ
ВЫБРАТЬ 9 КАК Количество ОБЪЕДИНИТЬ ВСЕ
ВЫБРАТЬ 10 КАК Количество
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ ПЕРВЫЕ 5
    КоличестваБобинПо30Метров.Количество * 30 + КоличестваБобинПо70Метров.Количество * 70 КАК НабраннаяДлина,
    КоличестваБобинПо30Метров.Количество КАК БобинПо30Метров,
    КоличестваБобинПо70Метров.Количество КАК БобинПо70Метров
ИЗ
    Количества КАК КоличестваБобинПо30Метров
        ВНУТРЕННЕЕ СОЕДИНЕНИЕ Количества КАК КоличестваБобинПо70Метров
        ПО (КоличестваБобинПо70Метров.Количество <= &ОстатокБобинПо70Метров)
            И (КоличестваБобинПо30Метров.Количество <= &ОстатокБобинПо30Метров)

СГРУППИРОВАТЬ ПО
    КоличестваБобинПо30Метров.Количество * 30 + КоличестваБобинПо70Метров.Количество * 70,
    КоличестваБобинПо30Метров.Количество,
    КоличестваБобинПо70Метров.Количество

ИМЕЮЩИЕ
    &НеобходимаяДлина <= КоличестваБобинПо30Метров.Количество * 30 + КоличестваБобинПо70Метров.Количество * 70

УПОРЯДОЧИТЬ ПО
    НабраннаяДлина


(49) Ты же понимаешь, что тут жесткая граница сверху: для заказа более 700 метров не посчитает? Да и каждый чих по формату бобин будет вызывать переделки.

Количество циферок можно добавить. Количество наборов тут 2 ,
т.е. с 3мя номенклатурами будет уже не очень оптимально.Можно их добавить.Когда номенклатур будет больше, чем наборов опять же не оптимально отрабатывать будет. Остается формировать запрос динамически.Для конкретной задачи может и 4-5 наборов будет достаточно.

ВЫБРАТЬ
    70 КАК Длина
ПОМЕСТИТЬ Ном

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    30
    
ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    5

;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
    МИНИМУМ(Ном.Длина) КАК Длина
ПОМЕСТИТЬ МинимальнаяДлинаБабины
ИЗ
    Ном КАК Ном
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
    0 КАК Количество
ПОМЕСТИТЬ Циферки

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    1

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    2

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    3

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    4

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    5

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    6

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    7
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
    МИНИМУМ(Циферки.Количество) КАК Количество
ПОМЕСТИТЬ МаксимальноеКоличествоМинимальныхБабин
ИЗ
    МинимальнаяДлинаБабины КАК МинимальнаяДлинаБабины
        ВНУТРЕННЕЕ СОЕДИНЕНИЕ Циферки КАК Циферки
        ПО (МинимальнаяДлинаБабины.Длина * Циферки.Количество >= &НужныйМетраж)
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
    Циферки.Количество
ПОМЕСТИТЬ ЦиферкиКоторыеНужны
ИЗ
    Циферки КАК Циферки
        ВНУТРЕННЕЕ СОЕДИНЕНИЕ МаксимальноеКоличествоМинимальныхБабин КАК МаксимальноеКоличествоМинимальныхБабин
        ПО Циферки.Количество <= МаксимальноеКоличествоМинимальныхБабин.Количество
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
    Ном.Длина,
    ЦиферкиКоторыеНужны.Количество
ПОМЕСТИТЬ Наборы1
ИЗ
    Ном КАК Ном,
    ЦиферкиКоторыеНужны КАК ЦиферкиКоторыеНужны
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
    Наборы1.Длина,
    Наборы1.Количество,
    Наборы11.Длина КАК Длина1,
    Наборы11.Количество КАК Количество1
ПОМЕСТИТЬ Наборы2
ИЗ
    Наборы1 КАК Наборы1
        ВНУТРЕННЕЕ СОЕДИНЕНИЕ Наборы1 КАК Наборы11
        ПО Наборы1.Длина <> Наборы11.Длина
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
    Наборы2.Длина,
    Наборы2.Количество,
    Наборы2.Длина1,
    Наборы2.Количество1,
    Наборы2.Длина * Наборы2.Количество + Наборы2.Длина1 * Наборы2.Количество1 КАК Рез1
ПОМЕСТИТЬ Рез
ИЗ
    Наборы2 КАК Наборы2
ГДЕ
    Наборы2.Длина * Наборы2.Количество + Наборы2.Длина1 * Наборы2.Количество1 >= &НужныйМетраж

СГРУППИРОВАТЬ ПО
    Наборы2.Длина,
    Наборы2.Количество,
    Наборы2.Длина1,
    Наборы2.Количество1
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
    МИНИМУМ(Рез.Рез1) КАК Минимум
ПОМЕСТИТЬ Рез2
ИЗ
    Рез КАК Рез
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ ПЕРВЫЕ 1
    Рез.Длина,
    Рез.Количество,
    Рез.Длина1,
    Рез.Количество1,
    Рез.Рез1
ИЗ
    Рез КАК Рез
        ВНУТРЕННЕЕ СОЕДИНЕНИЕ Рез2 КАК Рез2
        ПО Рез.Рез1 = Рез2.Минимум

(51) Да нет там ограничения по метражу. Есть ограничение на количество наборов в таблице из которой будем выбирать. Вот например цифр уже 10000.

ВЫБРАТЬ
    0 КАК Количество
ПОМЕСТИТЬ Циферки

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    1

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    2

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    3

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    4

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    5

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    6

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    7

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    8

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    9
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
    Циферки.Количество * 10 + Циферки1.Количество + Циферки2.Количество * 100 + Циферки3.Количество * 1000 КАК Поле
ПОМЕСТИТЬ ЦиферкиМного
ИЗ
    Циферки КАК Циферки,
    Циферки КАК Циферки1,
    Циферки КАК Циферки2,
    Циферки КАК Циферки3
;

А если пойти от математики:

30х+70y=a , где а - необходимое кол-во метров

Тогда, преобразовав, получаем:

y= (a-30x)/70;

Теперь, варьируя целочисленные значения для X, от нуля до a/30 , получаем значения для y. Как только y стал без дробной части - выход из цикла.

(54) а = 155.

(54) Это не математика, а арифметика -_- Не решаются такие задачи таким образом. Это конкретный пример линейного программирования.

(30) Реализовано лет 5-6 назад. Лежит на инфостарте.

(57) Ожидаемо :(

(0) Давно бы перебором (2 цикла с отсевом заведомо неподходящих вариантов) сделали - полчаса/час.
А то развели обсуждение выеденного яйца на 2 дня.

(0) Такая задача запросом не решается.
К таким задачам (которые не рашаются на запросах) относится и задача про банкоматы и купюры.
Так что пользуйся циклами)).
http://informatics.mccme.ru/mod/book/view.php?id=815

Кстати, знатоки симплекс-метода, приведите, плиз, пример решения задачи, чтобы не получить, что надо 0.456 бухты 30м и 0.2227 бухты 70м. Я вот чего-то не нашёл реализации симплекс-метода в целых числах.

(61) Его и нет в природе.

(57) Эээ, да там чем же через ВК. Так неспортивно :)

(62) То-то и оно)

(63) Не знаю, какую Вы смотрели, а у меня на инфостарте без ВК (т.к. не умею их делать). Если хотите посмотреть - киньте письмо мне на мыло (в профиле).

(62) https://ru.wikipedia.org/wiki/%C0%EB%E3%EE%F0%E8%F2%EC_%C3%EE%EC%EE%F0%E8

(65) Хм, странно, не нашлось. Но смотреть и не надо сам напишу. Все равно это скорее разминка для мозгов :)

(66) В алгоритме Гомори число неравенств может расти экспоненциально.

(68)Если использовать отсечение, то в худшем случае будет n^(2*n-m) на каждом шаге. Конечно, количество итераций может быть очень большим, но оно точно конечно.

Метод Гомори старый и известно, что в целочисленных задач он мало когда работает.

(70) В чем может быть выражена его "не работает"? Думаю, он может оказать затратнее перебора в худшем случае.

(0) Бухты всего двух видов? a1 и a2
Находишь НОК(a1,a2) - наименьшее общее кратное.
Для 30 и 70 - это 210
Вычисляешь k1 = НОК(a1,a2)/a1, k2 = НОК(a1,a2)/a2
Для 30 и 70 - это 7 и 3

Далее делаешь табличку (регистр сведений) размерности k1*k2
b1, b2, b1*a1+b2*a2, где b1  от 0 до k1 и b2 от 0 до k2

при подборе x метров берешь остаток X от деления на 2НОК
дальше уже можно запросом

(72) ИМХО, это уже за гранью, когда добавления новой номенклатуры требует переделать метаданные и перезаполнить регистр :)

(60) Да, тоже подумал про выдачу суммы оптимальными купюрами

(73) Это не за гранью, это новое ТЗ и новые бабосы :)

(75) Я подумал сначала, что это твоя тема: Плохой код как способ защиты своей работы :)

(76) Кстати, в случае более двух номенклатур алгорим из (72) вполне себе дополняется, а не выкидывается.

Сначала находим НОД(A1, A2,...An) - наибольший общий делитель.
Если он не равен 1, то сокращаем все на этот НОД.
Грубо говоря, если у нас все числа четные, то подобрать можно только четные.
Получаем НОД(A1, A2,...An) =1.
Находим минимальные Аi, Aj, такие , что НОД (Ai, Aj) =1
Для этих Ai, Aj применяем алгоритм из (72), так число, больше 2*Ai*Aj можно точно подобрать с помощью Ai, Aj
Для чисел, меньших 2*Ai*Aj пишем что-то вроде аналога решета эратосфена.