(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.