Нужен алгоритм решения задачи о ранце(линейное программирование). Нужен ОЧЕНЬ быстрый алгоритм. Подозреваю, что таковым является метод ветвей и границ, но что это такое — не знаю. Есть вот такой алгоритм, но он слишком медленный:

void f()
{
  for (int i=deep++;i<n;i++)
  {
    if (in[i]==0)
    {
      if (mass[i]+currentm<=m)
      {
    in[i]=1;
    currentm+=mass[i];
    currentp+=price[i];
    f();
    if (currentp>bestprice)
    {
      bestprice=currentp;
      memcpy (bestin,in,sizeof (char)*n);
    }
    in[i]=0;
    currentp-=price[i];
    currentm-=mass[i];
    deep--;
      }
    }
  }
}

где bestprice — это лучшая цена, а bestin — массив тех предметов, которые надо брать.
mass и prise массивы соответственно масс и цен. n — максимальное число предметов, а m — максимальная масса.
Может быть кто-нибудь улучшит этот алгоритм?

В смысле — максимизировать цену, не превышая макс. массу?
В случае, когда каждый груз в единственном экземпляре, а диапазон весов не слишком велик, задача решается методом динамического программирования. Читайте всякие топики "задача о загрузке рюкзака", "... загрузке машины и т.п.". Как решается в случае множественности — уже не помню, а вспоминать нет времени

Вкратце идея такова: пусть первые N грузов уже уложены оптимально (вернее, пусть есть только первые N грузов и для них задачи с ограничением по весу от 0 до изначально стоящего перед нами ограничения MaxWeightПоУсловию уже решены). Тогда добавим в задачу N+1-й груз и зададимся каким-то новым ограничением MaxWeight. Если мы его(груз) берем, то оптимальное решение новой задачи будет равно Price[N+1]+решение задачи MaxPrice(N,MaxWeight-Weight[N+1]), то есть решению уже рассмотренной ранее подзадачи для N грузов и макс. веса MaxWeight-Weight[N+1]. Если же новый груз не берем, то оптимальное решение равно MaxPrice(N,MaxWeight). То есть для данного maxWeight надо из этих 2 вариантов выбрать максимум.

Теперь пускаем цикл (при том же значении N+1) MaxWeight=0..MaxWeightПоУсловию и для каждого из осуществляем такой выбор максимума из 2 вариантов (ясно, что иногда может оставаться лишь 1 вариант — например, когда кроме N+1 груза, если его взять, не влезет вообще ничего). Получаем линейку решений уже для N+1 грузов и MaxWeight=0..MaxWeightПоУсловию.
Потом увеличиваем N и повторяем процедуру.
Результаты решения подзадач удобно хранить в таблице.

В конце надо будет взять клетку MaxPrice(Nгрузов, MaxWeightПоУсловию) и пройти "назад" по таблице, на каждом шаге из двух кандидатов, из которых мы могли попасть в текущую клетку, легко можно выбрать того, из которого мы в действительности в нее пришли (опять сравнить два варианта). Так получим, какие грузы мы брали, а какие-нет.

Надеюсь, не слишком сумбурное объяснение? Если что, пишите gmm@bashnet,ru.

Slicer

Здравствуйте, Keith, Вы писали:

Нужен алгоритм решения задачи о ранце(линейное программирование). Нужен ОЧЕНЬ быстрый алгоритм. Подозреваю, что таковым является метод ветвей и границ, но что это такое — не знаю. Может у кого-нибудь уже есть готовый и работающий алгоритм? В предыдущих топиках я смотрел, но там только одна задача о раскрое, которая не подходит и один исходник, который не компилится =( Поищите,пожалуйста, у кого может быть.

Здравствуйте, Keith, Вы писали:

Посмотри эту ветку

Автор:
Дата: 16.11.02

.

Здравствуйте, Keith, Вы писали:

K> Нужен алгоритм решения задачи о ранце(линейное программирование). Нужен ОЧЕНЬ быстрый алгоритм. Подозреваю, что таковым является метод ветвей и границ, но что это такое — не знаю. Есть вот такой алгоритм, но он слишком медленный:
K> Может быть кто-нибудь улучшит этот алгоритм?

Это классическая задача бинарного программирования, я достаточно долго ей занимался и могу сказать так: она решается за разумное время известными (мне) способами при количестве предметов и ограничений не более 50-60. Если повезет — то и для большего количества, но для 120 переменных у меня не решилась за 3 дня Может существует более быстрое решение — я не знаю

Могу предложить статью (вышлю по e-mail) если что — пиши nikholas@mail.ru