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

Цитата 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

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

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

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