Решение полным перебором

 

Думаю, покупатель будет вести себя следующим образом: возьмёт первый товар (а все товары пронумерованы), затем следующий из оставшихся, затем следующий из оставшихся и т.д. пока не заберет все товары.

Затем он выложит последний и снова попытается увеличить количество товаров, но это не имеет смысла, так как последний товар он только что выложил. Тогда он выложит предпоследний и положит в сумку последний, и у него получится новая совокупность товаров.

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

Теперь то же самое но немного более строго.

Предположим, что у покупателя есть сумка в которой столько же отделов сколько товаров и эти отделы пронумерованы. Каждый раз когда покупатель кладет в сумку новый товар, образуется новая совокупность товаров которая может оказаться искомой. Для того, чтобы это выяснить покупатель после того, как положил товар, взвешивает сумку и выясняет две вещи: может ли он это оплатить и если да, то весит ли сумка больше, нежели запомненный вес. А первоначально сумка не весит ничего.

У покупателя две проблемы:

Большая. Как обеспечить полный перебор всех допустимых совокупностей товаров. Маленькая. Как сделать так, чтобы не было повторов. Ведь может так получится, что он возьмёт одни и те же товары, но в разном порядке. Это конечно не беда, но лишняя работа. Я полагаю, что эти две проблемы решаются следующим образом:

В первом отделе должны побывать все товары. В отделе с номером i должны побывать все товары с номерами на меньшим чем i. Таким образом для каждого отдела с номером i будут получены все допустимые комбинации товаров в остальных отделах с номерами большими чем i и соответственно для отдела с номером 1 будут получены вообще все возможные комбинации.

Наверное стоит привести конкретный пример работ алгоритма. Возьмём следующее множество: 1, 2,3. Для этого множества алгоритм даст следующие комбинации:

 

(1), (1,2), (1, 2,3), (1, 2,3), (1,3)

(2), (2,3)

(3)

 

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

program example;

uses crt;

var

b,s: array [1. .100] of word;

a: array [1. .100] of record

cost,ves: word;

end; {Массив магазин}

sum_ves,sum_cost,max,money,level, i,n: integer;

function add_element (d: integer): integer;

var

i: integer;

q: boolean;

begin

repeat

{Ищем пока не найдём}

q: =true;

{проверка есть такой товар или нет}

for i: =1 to level do

if s [i] >=d then q: =false;

if q then add_element: =d

else

begin

d: =d+1;

{проверка, не вышли ли мы за допустимые границы}

if d>n then

begin

add_element: =0;

q: =true;

end;

end;

until q

end;

begin

clrscr;

read (n);

for i: =1 to n do

begin

writeln ('Элемент номер - ', i);

write ('Введите его вес - '); read (a [i]. ves);

write ('Введите его цену - '); read (a [i]. cost);

b [i]: =i;

end;

write ('Сколько денег в наличии - '); read (money);

clrscr;

level: =1; max: =0;

while b [1] <n do

begin

{Поиск элемента не использованного на этом уровне}

b [level]: =add_element (b [level]);

if b [level] >0

then

begin

s [level]: =b [level] ;

level: =level+1;

sum_ves: =0; sum_cost: =0;

for i: =1 to n do

if s [i] <>0 then

begin

sum_ves: =sum_ves+a [s [i]]. ves;

sum_cost: =sum_cost+a [s [i]]. cost;

end;

if (max<sum_ves) and (sum_cost<=money) then max: =sum_ves;

end

else

begin

{освобождаем отдел}

s [level]: =0;

b [level]: =level;

level: =level-1;

end;

end;

write ('Наибольший вес - ',max);

end.

 

Бектрекинг

 

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

 

{освобождаем отдел}

s [level]: =0;

b [level]: =level;

level: =level-1;

Заметьте, что этой группе операторов абсолютно без разницы причина по которой к неё обращаются. Поэтому добавим в программу ещё одну причину обращения к этой группе. А именно

Если сумма набранного товара больше имеющейся наличности

ТО освобождаем отдел.

Заметим, также, что группа операторов "Освобождаем отдел" повторяется дважды поэтому есть смысл организовать её в виде процедуры. А вот как выглядит теперь программа:

 

program example;

uses crt;

var

b,s: array [1. .100] of word;

a: array [1. .100] of record

cost,ves: word;

end;

sum_ves,sum_cost,max,money,level, i,n: integer;

procedure back;

begin

s [level]: =0;

b [level]: =level;

level: =level-1;

end;

function add_element (d: integer): integer;

var

i: integer;

q: boolean;

begin

repeat

q: =true;

for i: =1 to level do

if s [i] >=d then q: =false;

if q then add_element: =d

else

begin

d: =d+1;

if d>n then

begin

add_element: =0;

q: =true;

end;

end;

until q

end;

begin

clrscr;

read (n);

for i: =1 to n do

begin

writeln ('Элемент номер - ', i);

write ('Введите его вес - '); read (a [i]. ves);

write ('Введите его цену - '); read (a [i]. cost);

b [i]: =i;

end;

write ('Сколько денег в наличии - '); read (money);

clrscr;

level: =1; max: =0;

while b [1] <n do

begin

{Поиск элемента не использованного на этом уровне}

b [level]: =add_element (b [level]);

if b [level] >0

then

begin

s [level]: =b [level] ;

level: =level+1;

sum_ves: =0; sum_cost: =0;

for i: =1 to n do

if s [i] <>0 then

begin

sum_ves: =sum_ves+a [s [i]]. ves;

sum_cost: =sum_cost+a [s [i]]. cost;

end;

if sum_cost>money then back

else

if (max<sum_ves) then max: =sum_ves;

end

else back;

end;

write ('Наибольший вес - ',max);

end.

Заключение

 

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

Условие: Дана фигура из картона. Можно ли её разрезать на заданные фигуры (и по форме и по размеру)

Определим понятие разреза следующим образом: разрез это линия определённой длины проведённая по фигуре с началом в определённой точке и в определённом направлении. Дополнительные знания формы исходной фигуры и форм требуемых фигур позволят сократить множество допустимых разрезов и сделать его пусть большим, но конечным.

Тогда задача становится задачей полного перебора. Бектрекинг накладывается на неё очень просто и естественно. Пусть мы провели очередной разрез. Проверим, дал ли он в совокупности с другими разрезами фигуру. Если да, то проверим, входит ли эта вырезанная фигура в множество искомых. Если нет, то данное множество разрезов тупиковое.

Литература

 

1. Вострикова З.П. и др. "Программирование на языке "БЕЙСИК" для персональных ЭВМ". Машиностроение, 1993г.

2. Гохман А.В. и др. "Сборник задач по математической логике и алгебры множеств", издательство Саратовского Университета, 1969г.

3. Гусев В.В. Основы импульсной техники. М. Советское радио, 1975

4. Касаткин В.Н. "Информация, алгоритмы, ЭВМ", М. Просвещение, 1991г.

5. Машовцев В.А. Вступительные экзамены по информатике // Информатика. 1997, №13

6. Орлов В.А. О вступительных экзаменах по информатике // Информатика, 1997, №15

7. Яснева Г.Г. Логические основы ЭВМ // Информатика и образование, 1998, №2

8. Лыскова В.Ю., Ракитина Е.А. Логика в информатике, М. Информатика и образование 1999

9. Шауцкова Л.З. “Решение логических задач средствами алгебры логики”, газета Информатика 1999, №5.