большое количество комбинаций и выбор оптимального решения

[Racheengel]

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

Грубо получается: P * (K * Bp), P - это продукты, Bp - кол-во бочек для продукта P, К - кол-во комбинаций проверки.
Например, если Р=10, Bp (грубо в половину) =5, K = 10..20 step 0.1 = 100, то имеем: 10 * 5 * 100, всего 5000 вычислений.
Секунда? Полсекунды?

[ssoft]

Ну как-то складывается впечатление что, мол, да тут легко, общих фраз вполне достаточно Я так не считаю, задачка трудная (хотя возможно и стандартная).

Основная сложность в четком определении
- перечня варьируемых параметров и области их определения - в данном случае 9 переменных из области [10...20].
- целевой функции, которая рассчитывается по варьируемым параметрам - это может быть остатки сырья, стоимость оставшегося сырья и т.д.
- ограничивающих параметров - например, ограниченный объем сырья (не более N бочек) и т.п.

Как только есть метод расчета целевой функции с проверкой на выполняемые ограничения, можно использовать любой понравившийся метод оптимизации, например, отсюда http://www1.icsi.berkeley.edu/~storn/code.html или взять готовый продукт http://www.iosotech.com/ru/products.htm или Mathcad.

[demal]

вот с ограничениями в условии задачи и трудности - нет ограничения на количества сырья. А в этом случае ничего кроме как тупого перебора не остается.

[Igors]

- целевой функции, которая рассчитывается по варьируемым параметрам - это может быть остатки сырья, стоимость оставшегося сырья и т.д.

Это не катит для комбинаторики. Напр какой-то путь на предпоследнем шаге худший - но после выполнения последнего шага оказался лучшим.

вот с ограничениями в условии задачи и трудности - нет ограничения на количества сырья. А в этом случае ничего кроме как тупого перебора не остается.

Ну что ж так быстро-то программист опускает руки?  Вроде еще не "пользователь Qt"

Кажется понял как решать, вот набросок

Код

C++ (Qt)
// структура элемента
struct CReminder {
 std::vector<int> mRem;   // остатки по каждому сырью (0..999)
 int mSum;                       // сумма остатков
 int mTblIndex;                 // индекс в предыдущей таблице
 std::vector<int> mAdd;   // число произведенных продуктов по каждому сырью
};
 
// подсчет новых остатков
int TryAdd( const CReminder & rem, std::vector<int> & data )
{
  int result = 0;
  assert(rem.,Rem.size() == data.size());
  for (size_t i = 0; i < data.size(); ++i) {
    int a = rem.mRem[i];
    if (data[i]) 
      a = (a + data[i]) % 1000;
    result += a; 
  }  
  return result;
}
 
// шаг (вычисление остатков при производстве 1 продукта)
void Step( int productNo, const std::vector<float> & num, std::vector<int> & data )
{
 assert(data.size() == NUM_RAW);
 std::fill(data.begin(), data.end(), 0);
 
 for (size_t i = 0; i < NUM_RAW; ++i)  // по всем видам сырья
  data[i] = std::remainder(GlobalTable[productNo][i] * num[i], BARREL_SIZE) / BARREL_SIZE * 1000;
}
 
void Process1Product( int productNo )
{
   int numRaw = 0;
   for (size_t i = 0; i < NUM_RAW; ++i)  // кол-во сырья для этого продукта
     if (GlobalTable[productNo][i]) ++numRaw;
 
  float limit[2] = { DEF_LOW_LIMIT,  // 10
                          DEF_HI_LIMIT } // 20
  if (numRaw > 1) limit[0] = 0.0f;
 
  int rawIndex = 0;
  Process1ProductRecursive(productNo, 0, rawIndex, numRaw, limit);        
}
 

Ну все расписать не смогу - там довольно много. Смысл в том что вложенные переборы (Recursive) только по столбцу когда продукт использует 2 или больше сырья. Остальное как говорилось раньше - тот же контейнер остатков, только по всем видам сырья

[kuzulis]

Ого, да тут целый матан. Шо-то я забыл уже все, программирование отупляет. 

[ksv-uk]

Igors, спасибо большое за ваше участие. В программу пока не вникаю, тут с алгоритмом сначала нужно разобраться.

Пытаюсь вникнуть в вашу идею.Пишу пока без глубокого осмысления (первая прикидка). Если все верно понял, вы предлагаете(описываю словесно):

1) В цикле идем от 1 до 100 ((20-10/0.1=100). Если диапазон решений будет другой, соотв. границы будут другие
2) Берем 1 продукт, ищем остатки сырья 4, без учета целых бочек (заносим остатки в массив№1 (массив 9(кол-во сырья) на 100 (вариантов))
3) Берем 2 продукт , ищем остатки сырья 1, 3, 8 без учета целых бочек (заносим остатки в массив №2)
и.т.д для всех продуктов.
В итоге получаем 9 массивов (9Х100) в которых будут сохранены остатки сырья, если бы производили продукты отдельно друг от друга.
Теперь нужно получить суммы остатков.
1) цикл по видам сырья (1 до 9)
2) цикл по массивам (1 до 9)
3) цикл по вариантам (1 до 100)

Получается 9*9*100 = 8100

Ищем комбинацию с наименьшим остатком по всем видам сырья.

По моему что-то напутал, ушел в размышления...

[ssoft]

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

В этом варианте не решается задача нахождения минимума, а реализуется последовательное выравнивание остатков, при этом результат будет зависеть от порядка рассмотрения продуктов. Но действительно, если это прикладная задача, то можно ограничится таким подходом. Если нужно точное решение, то так решить не получится.

[Igors]

Ого, да тут целый матан. Шо-то я забыл уже все, программирование отупляет.  

Ага, "сборки", "ключики", std::срань и.т.п. - где уж тут чего-то помнить  

Пытаюсь вникнуть в вашу идею.

Она не моя. Есть классическая "задача о монетках"

Есть N разных монет, напр 1 (рубль), 2, 5 и.т.п. Требуется набрать нужную сумму из минимального кол-ва монет.

Казалось бы - ну без перебора никак. Но лучшее решение есть. Захотите - нагуглите, вещь известная.

Здесь я пытался сделать то же самое. Для каждого продукта есть "таблица остатков" (контейнер). Элемент хранит остатки по каждому сырью и суммарный. Индекс элемента совпадает с суммарным остатком. Напр 5-й элемент имеет mSum = 5. Остатки меряем от 0 до 999 для одного продукта, для 10 продуктов от 0 до 9999. Пустые эл-ты (такого остатка еще не было) помечаем напр mSum = -1

Process1Product перебирает все комбинации "по столбцу". Напр продукт 7 использует 3 вида сырья. На какой-то итерации 3 циклов у нас напр 5.0, 4.2, 8.1 по каждому сырью - переводим их в остатки (как если бы все бочки еще целые). Пытаемся добавить эти остатки к каждому в предыдущей таблице остатков. При этом всякий раз по mSum мы попадаем на какой-то индекс в новой таблице. Если он пустой - записываем туда новый эл-т, иначе просто ничего не делаем - такой остаток уже есть, неважно как он получен.

Update: деталь реализации. После вычисления mSum провериться был ли уже такой при производстве данного продукта. Чтобы избегать дороговатой операции "добавить к каждому"

[Igors]

т.е. для каждого продукта проверять комбинации только с задействованными для него бочками плюс остатки с предыдущего шага.

только плюс "каждый с каждым" Кстати задача "разпоточивается", пусть и с некоторыми накладными расходами

Да, и вообще-то интересно как написать "общий for" для перебора в столбце. Ну вот, сейчас опять пойдет "вода" 

[Racheengel]

не надо "каждый с каждым" - остатки то суммируются...
выиграем мизер, потеряем время..

[Igors]

не надо "каждый с каждым" - остатки то суммируются...
выиграем мизер, потеряем время..

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

(20%. 45%)
(32%. 91%)
и.т.д (первый котейнер)

А для второго продукта

(11%. 12%)
(32%. 21%)
и.т.д (второй котейнер)

Новые комбинации остатков могут образоваться при сложении каждого эл-та первого контейнера с каждым эл-том второго. Поэтому "каждый с каждым" - квадратичный перебор

[Racheengel]

После того, как для первого продукта остатки посчитались, их надо добавлять к последующим рассчетам и с их учетом подбирать следующие расходы для продуктов 2, 3 и пр.

[Igors]

После того, как для первого продукта остатки посчитались, их надо добавлять к последующим рассчетам и с их учетом подбирать следующие расходы для продуктов 2, 3 и пр.

На это ответ уже был

Это не катит для комбинаторики. Напр какой-то путь на предпоследнем шаге худший - но после выполнения последнего шага оказался лучшим.