Задача о рюкзаке

Не подскажите ли следующий алгоритм:
дано n целых ai>0 и целое S>0. Нужно найти подмножество ai, сумме которого равна S или показать, что такого нет.

???

самый простой вариант - это полный перебор.
типа есть у тебя n твоих предметов. ты перебираешь все подмножества из этих предметов и смотришь сумму весов выбранных.
перебор делается очень просто. либо рекурсией, либо берешь строку из n-битов(байтов, слов...) каждый i-ый елемент строки, если ноль, то предмет не взят, если 1, то предмет взят. вот и все.

Сообщение отредактировано: experimenter - 28.04.03, 01:58

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

А разве динамическое решение не пройдет?
Т.е. ставим первый доступный вес, потом смотрим, какие следующие доступные веса и т.д. Должно работать   :

Так это простая задача о рюкзаке. Она решается без перебора. Перебором решается немного другое: n предметов с определенной стоймостью и весом. Выбрать несколько из них так, чтобы их суммарная стоимость была максимальной при заданном весе! Вот это задача о рюкзаке, которая классифицируется как NP-hard  8)

Сообщение отредактировано: tserega - 29.04.03, 10:52

динамическое программирование по-моему тоже самое, что и перебор.

я имел ввиду данный случай.

Цитата tserega, 29.04.03, 14:49:33

А разве динамическое решение не пройдет?
Т.е. ставим первый доступный вес, потом смотрим, какие следующие доступные веса и т.д. Должно работать   :

Так это простая задача о рюкзаке. Она решается без перебора. Перебором решается немного другое: n предметов с определенной стоймостью и весом. Выбрать несколько из них так, чтобы их суммарная стоимость была максимальной при заданном весе! Вот это задача о рюкзаке, которая классифицируется как NP-hard  8)

1) динамическое програмирование подойдет
только то что вы нарисали это жадный алгоритм а не динамический

2) жадный тут не идет он подходит только для непрерывных задач

3) да помоему NP complete a ne hard

Сообщение отредактировано: esperanto - 29.04.03, 14:42

Цитата esperanto, 29.04.03, 18:41:44

1) динамическое програмирование подойдет

как?

Цитата esperanto, 29.04.03, 18:41:44

да помоему NP complete a ne hard

NP-compleate - решаемо без полного перебора (возможно, динамически). Рассматриваемая задача, безусловно, NP-compleate, а с стоимостью предметов - hard.

Цитата Demo_S, 29.04.03, 19:18:23

как?

Если есть веса w1, w2, .. wn, и клетка Can[I] заполнена и следующий возможный предмет j, то и клетка Can[I + wj] тоже должна быть заполнено. Для инициализации
Can[0]:=True; {вес 0 получить можно}
Если надо пролучить и сами номера предметов, то при каждой итерации надо в еще один массив записывать, благодаря какому предыдущему сумарному весу мы получили текущий.

чем данная реализация отличается от перебора?

насколько я понял, также перебираются все комбинации предметов (без учета порядка следования) только решается не для 1 веса, а сразу для всех:)

Отличается тем, что у тебя сложность алгоритма O(n*m), а не что-то типа O(n!)
n - число предметов, m - вес, который надо получить. При больших n динамический метод НАМНОГО лучше.

если правильно делать перебор (исключая перестановки, которые и дают факториал) то будет как раз то же...

Цитата tserega, 30.04.03, 21:38:29

NP-compleate - решаемо без полного перебора (возможно, динамически). Рассматриваемая задача, безусловно, NP-compleate, а с стоимостью предметов - hard.

NP complete это
1)задача класса NP это значит имея решение можно проверить что оно правильно за полиномиальное время
2) любую задачу этого класса можно решить с её помощью и полиноминальной редукцией на нее

Вижу, у вас на форуме упомянули о методе Greedy
Подскажите пожалуйста его формулировку и если можно само описание данного метода

заранее благодарна

uvolga@hotbox.ru

Жадный сетод - на каждом шаге берем то, что на данный момент кажется самым лучшим (для задачи о рюкзаке, например, можно брать предмет, у которго отношение цена/вес будет максимальным)

Так тема и зависла...
У меня вот возникла подобная проблема.
Т.е. тоже задача о рюкзаке, но с немного модифицированым условием.
Таким как тут:
Процедура поиска
(к сожалению топик кажется тоже засох )
В Инете я среди общего мусора нашел вот такой алгоритм:
http://www.mgopu.ru/PVU/2.1/Recurs/BacketT...rn/task_ruc.htm
но к сожаления я так и не понял ничего из ихней схемы.
Может к-нить помочь?

Или вот что я думал:
если судя по той инфо, которую я накопал в Инете такая задача решается только методом полного перебора, то возникли такие наброски алогритма:
1. Высчитываем количество комбинаций С по формуле Бернулли (не перестановок! гже просто факториал) группы K элементов из множества N.
2. Формируем массив размерностью полученого числа С.
3. Поочереди в цикле i=1:C вызываем хитрую ф-цию (см. ниже), парсим ее результат, получаем комбинацию и высчитываем для каждой полученной комбинации её коеф. оптимальности и заносим в масив из п.2.
4. Находим в массиве максимальное значение. Порядковый номер ячейки масивва и будет искомая комбинация. (опять вызываем хитрую ф-цию - которая по-сути вернет уже готовый результат)

Вся проблема в п.3, а именно: нужна вот та самая хитрая ф-ция на вход которой подается 3 параметра: K, N, I которая бы возвращала вектор (ну хотя-бы в виде стринга, со значениями разделенными запятой) порядковых номеров элементов из множества N соотв. I-той комбинации.

Например:
N = 4
K = 2

Вообще все комбинации (4!/(2!*2!) = 6 штук):
1, 2
1, 3
1, 4
2, 3
2, 4
3, 4

так вот:
f(4, 2, 2) - возвращает "1, 3"
f(4, 2, 5) - возвращает "2, 4"

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

Нет, ребята... Я тут вечерком подумал - лажа какая-то полная.
О каком полном переборе может ити речь?
Если, например, мне надо выбрать со склада 15 товаров, на котором их 25 видов по критерию: минимальная общая стоимость + общий вес не более 60 кг.
Количество комбинаций: 25!/15!/10! = 3268760 комбинаций!!!
Это ж сколько у меня мегабайт оперативки только масив критериев займет?! А?
А время?!!
Даже если учесть, что комп будет высчитывать 100 комбинаций в сек. (что маловероятно) то всеравно уйдет около 9-ти(!) часов времени! И это только для одногопокупателя, а их может быть десяток...

Хотелось бы услышать мнение Esperanto о даной проблеме. Может есть какй-то метод монте-карло (или как там его) который бы высчитывал искомую комбинацию хотя-бы на порядок быстрее, пусть даже с точностью где-то до 80%? Т.е. что-бы возвращаемый результат удовлетворял изначальному критерию по массе (что-бы человек смог унести товар) но вот по миним. стоимости уже пусть немножко привирает иногда - терпимо.

Есть целая группа методов - генетические алгоритмы, позволяют находить КВАЗИОПТИМАЛЬНЫЕ решения. Незаменимы именно для таких случаев, когда решение не обязательно должно быть самым лучшим, а вполне достаточно просто хорошего решения.

Инфу можно найти в инете - я бы и сам тебе поискал, но превысил квоту по зарубежному траффику.

Если будут вопросы по генетическим алгоритмам - задавай.

Насчет ГА, например фак и сорцы либы на http://sourceforge.net/projects/cpplibga/

Может посмотри здесь "задача о рюкзаке"

ну если автору хватит ОДНОЙ комбинации, там динпрог просто рулит, сложность О(N*N) а по последней ссылке требовалось найти ВСЕ, а значит полным (или неполным) перебором наши программы можно использовать, воткнув exit при нахождении первой комбинации.

Вот накатал на васике. (рюказчки).

Рюкзачок (Файл 3.17 Кб.)

Цитата Dr._S, 4.10.04, 07:46

Вот накатал на васике. (рюказчки).

Да нет. Совсем не то.
Тут, я так понял, просто задается макс. вес (напр. 100 кг.) и потом ищется комбинация вещей, которая бы не переваливала за опред. макс. критерий. (напр. 25 кг.)
Тут налицо простая однопараметрическая оптимизацмия.

Нужна же двухпараметрическая: не превышает макс. допустим. вес при этом миним. суммарная стоимось.

Chow,

Цитата

Тут, я так понял, просто задается макс. вес (напр. 100 кг.) и потом ищется комбинация вещей, которая бы не переваливала за опред. макс. критерий. (напр. 25 кг.)

, не то чтобы перевалила, а комбинация равная эту весу, ни больше, ни меньше. Не пойму какие проблемы, тебе находит комбинации, теперь сам проанализируй их на наименьшую стоимость. Заведи массив в котором индексом цены будет вес предмета и все, какие проблемы? Получи сумму всех комбинаций, сравни и вуаля.

Цитата Dr._S, 4.10.04, 12:59

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

ОК. попробую. спасибо. (хотя, мне надо именно что-бы не перевалила, а не больше-меньше)
Мне кажется, что это и есть полный перебор. Так что тут траблы с быстродействием будут. Хотя... Попробую. Тот вариант что вы прислали вроде-бы шустренько работает.

Chow,

Цитата

хотя, мне надо именно что-бы не перевалила, а не больше-меньше

, ну так и есть, я же написал

Цитата

...комбинация равная этому весу, ни больше, ни меньше...

Опять вы меня не поняли.
В вашем варианте производится поиск любых наборов элементов, суммарная масса которых точно соответств. заданой.
Мне же нужно: найти наборы состоящие точно из N элементов, суммарная масса которых не превышала бы (т.е. была бы <=) заданую.

Таких комбинаций будет ОЧЕНЬ много. И вот потом, мне надо будет из них выбрать одну - ту у которой суммарная стоимость (еще один дополнительный параметр наряду с массой) меньше всех!

Chow,

Цитата

Мне же нужно: найти наборы состоящие точно из N элементов, суммарная масса которых не превышала бы (т.е. была бы <=) заданую

, ну хорошо, сделай проверку (в поиске вариантов), если набран нужный вес и кол-во элементов = твоему N, то выводишь этот набор или записываешь, иначе - игнарируешь. И всё.

Цитата Dr._S, 6.10.04, 05:26

ну хорошо, сделай проверку (в поиске вариантов), если набран нужный вес и кол-во элементов = твоему N, то выводишь этот набор или записываешь, иначе - игнарируешь. И всё.

Да не набран нужный вес!!!
Мне не обязательно его точно набрать! Надо что-бы он был меньше заданого допустимого.

Добавлено Сегодня, 08:55
Бли-и-ин...
Ну сколько еще можно объяснять.
Делаю последнюю попытку и расжевываю все до последнего.
Допустим есть аэроклуб любителей-парашютистов. В нем состоит 100 чел.
И вот пришла в клуб заявка на международные юношеские соревнования по групповым прыжкам.
Правила проведения:
1. групповой прыжок проводится в составе 15 чел. (больше на борт просто самолет не может взять - всего 15 посадочных мест)
2. суммарный вес группы парашютистов не должен превышать 1130 кг. (иначе самолет не взлетит)
3. чем меньше сумарный (или средний) возраст группы - тем больше очков она получит за прыжок. (т.е. мастерство тоже учитывается, но даются колоссальные льготы на то, что прыгают юные участники, а не махровые мастера).

Теперь допустим все 100 членов клуба практически имеют одинаковый уровень мастерства.
И перед руководством стоит задача: выбрать из 100 клубней 15 таких человек, что-бы их общий вес не превышал 1130 кг., и при этом сумарный (или средний) возраст был как можно меньше!

(Тут я наплел немного про возраст - для ясности и простоты. На самом деле никаких льгот за возраст не дается, каждый участник клуба имеет другой показатель - уровень своего мастерства и руководству клуба надо выбрать 15 чел. - самых мастеровитых и что-бы не очень толстых...)

Chow, на кой х№" ты мне это объясняешь. Все и так понятно.

Цитата

Да не набран нужный вес!!!
Мне не обязательно его точно набрать! Надо что-бы он был меньше заданого допустимого.

, тогда еще проще, условие: кол-во_парашютистов = ограничение_по_кол-ву AND вес_отбираемых_парашютистов <= допустимый_вес

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

Цитата Dr._S, 6.10.04, 09:19

Chow, на кой х№" ты мне это объясняешь.

Для того, что-бы было более понятно.
Если я этим тебя (раз уж мы на ты) обидел - извини.

Цитата Dr._S, 6.10.04, 09:19

тогда еще проще, условие: кол-во_парашютистов = ограничение_по_кол-ву AND вес_отбираемых_парашютистов <= допустимый_вес

Условие то понятно, но куда его поставить? Неуж-то в тот алгоритм, что ты прикреплял?
Там, ИМХО, логика поиска не подойдет.
Насколько я понял у тебя там в цикле берется каждый элемент по очереди и во втором цикле (внутреннем) начинает прибавляться к каждому след. Потом условие: если сума меньше заданой - то добавление продолжается, если перевалила - то прекращается, если точно равна - то комбинация запоминается.
Все. Т.е. к-во возможных комбинаций в твоем алгоритме - N + (N-1) + (N-2) + ... 3 + 2 + 1 (т.к. внутренний цикл начин. не с 1, а с текущей позиции внешнего).
Я же считаю (см. посты выше), что необходимое к-во комбинаций (вычисляемое по формуле Бернулли) совсем другое.
Т.е. алгоритм не подходит по определению...

НО! Если я не прав, и если твой алгоритм корректно заработает внесением условия

Цитата Dr._S, 6.10.04, 09:19

кол-во_парашютистов = ограничение_по_кол-ву AND вес_отбираемых_парашютистов <= допустимый_вес

то я публично признаю, что я далек от комбинаторики, математики и численных методов вообще, а тебе поставлю большой жирный "+".
Так что будь-добр, если не тяжело - внеси необходимые изменения в свой алгоритм и прикрепи его еще раз.
Буду очень призначтелен и благодарен.

Chow, Все понял, тут немного не подходит мой алгоритм, т.к. условия поменялись, условие ограничение_по_кол-ву его меняет. Алгоритм надо менять. Намедни посмотрю.

Chow, посмотри своих парашютистов, только не говори, что не так.
Файло 3,77 Кб.

Ну вот... Что и требовалось доказать.
Задал 30 чел., группа - 8 чел. Запустил. Пождал 20 мин. и закрыл программу так и не дождавшись результата...

О чем я и толкую уже в этом топике давным давно - полным перебором такую задачу решить просто, но долго.
Существует ли иной, приближенный способ решения?
esperanto так и не высказал свою мысль по этому поводу...

Вродеж уже гововрили - Генетический Алгоритм. Даст тебе приближенное решение. Собсно, он и употребим в подобных (NP) задачах.

Chow,

Цитата

Ну вот... Что и требовалось доказать.
Задал 30 чел., группа - 8 чел. Запустил. Пождал 20 мин. и закрыл программу так и не дождавшись результата...

, у меня выполнилось за 31 сек. 1) не надо выводит на отоброжения в листе вариантов. (это тормозит) 2) Убрал Doevents(для ускорения).
Если поубирать навороты, то будет гораздо быстрее обрабатывать.

ребят,помогите,пожалуйста,у меня тоже зада о рюкзаке есть,но она не работает.

Имеется рюкзак вместимостью Vmax и N предметов с весами V1,…Vn и стоимостью C1,…,Cn. Требуется унести в рюкзаке предметы на максимальную суммарную стоимость.

program Project2;

{$APPTYPE CONSOLE}

uses
SysUtils;

type combination = array [byte] of byte;
var x, c, v,Xmax:combination;
m,n:byte;
i,Vmax,Cmax:integer;

procedure print;
var s,i:integer;
begin
s:=0;
for i:=0 to n do
if x[i]=1 then s:=s+v[i];
if s<Vmax then begin
s:=0;
for i:=0 to n do
if x[i]=1 then s:=s +c[i];
if s>Cmax then begin
Cmax:=s; Xmax:=x;
end;
end; end;

procedure Generate(k: integer);
var i: integer;
begin
if k=N then begin
Print;
end else
for i:=0 to M do begin
x[k+1]:=i;
Generate (k+1);
end;
end;

begin
write('n='); readln(n);
writeln('ves='); for i:=1 to n do read(v[i]);
writeln('st-'); for i:=1 to n do read(c[i]); readln;
writeln('vmestimost-'); readln(Vmax);
m:=2;
cmax:=0;
generate(0);

for i:=0 to n do
if xmax[i]=1 then write(' X=',i+1);
readln;
end.

Дьяволенок, а вы каким алгоритмом делаете?

Если принципом включения-невключения, то в FAQ скачайте лекции по структурам данных, там и принцип описан, и практически готовая программа на паскале.
FAQ: избранное часть 1 (и не последняя)

Если динамическим программированием, то, например, так.
Алгоритм решения описан в лекциях Котова по ДП
Сумма чисел в массиве, наиболее приближающаяся к необходимой

 const N=5;
    Ves=16;
    var
    M: array[1..N] of integer;
    C: array[1..N] of integer;
    T:array[0..N,0..Ves] of integer;
    sum,i,j,v:integer;
    begin
    M[1]:= 4; M[2]:= 5; M[3]:= 3; M[4]:= 7; M[5]:= 6;
    C[1]:= 5; C[2]:= 7; C[3]:= 4; C[4]:= 9; C[5]:= 8;
 
    T[0,0] := 0;
    for j := 1 to Ves do T[0, j] := 0;
    for i := 1 to  N do T[i, 0] := 0;
 
    for i := 1 to N do begin
      for j := 1 to Ves do begin
        if j >= M[i] then begin
          if  T[i - 1, j]> T[i - 1, j - M[i]]+C[i] then
             T[i,j]:= T[i - 1, j]
          else T[i, j]:= T[i - 1, j - M[i]]+C[i]; end
        else T[i, j]:= T[i - 1, j];
      end;
    end;
 
    sum:= Ves; v:=0;
 
    for i := N downto 1 do
      begin
        if T[i, sum] = T[i - 1, sum] then
           writeln (i, '---No')
        else
          begin writeln (i, '   ',M[i], ' ',C[i]);
                sum := sum - M[i];
                v:=v+M[i];
          end;
      end;
     writeln('cost=', T[N,Ves], ' ves=',v);
    readln;
    end.

Сообщение отредактировано: Swetlana - 07.11.11, 11:52

дело в том, что я ее делала не мам,так как в программирование плохо шарю)))вроде бы здесь мне сказали рекурсия используется

Добавлено 07.11.11, 12:05
сама*

Цитата

я ее делала не мам,

Мама делала? Тогда маме скажите, что в общей схеме алгоритма с возвратом после вызова рекурсии для следующего k+1-го предмета нужно делать возврат, т.е. выбрасывать k-й предмет из рюкзака.
Модификация алгоритма с возвратом для решения задач на максимум на примере рюкзака описана в лекциях по структурам данных...

не мама а сама)))

Добавлено 07.11.11, 12:24
спасибо за лекции)))

а решал кто нибудь данную задачу методом ветвей и границ?

JustInCase, не ты уникальный чел, и такого никто не делал тыцай сюда

Ещё один вариант задачи на рюкзачную тематику - а вдруг у Светланы в копилке такого нет

Из бесконечного потока (длинного массива) натуральных чисел в диапазоне 1..N найти (ровно) K первых чисел, сумма которых равна N.
Пример: N = 10, K = 3
3 1 7 4 2 5... = > 1 7 2

Такой нет, пасибки

Скрытый текст

Сейчас немножко не до задачек стало, со вчерашнего дня... Вот немножко тьма рассеется, и в небе солнце заалеется, и я, конечно, вернусь в Алгоритмы