, перед тим як покласти товар у сумку будемо перевіряти чи немає його в сумці вже. Звучить безглуздо звичайно, але справа в тому, що реально ми будемо працювати не в магазині з сумкою, а з масивами і знищувати елемент масиву "магазин", а потім його відновлювати - це зайва робота, простіше здійснювати названу вище перевірку.
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]
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
end
else
begin
{звільняємо відділ}
s [level]: = 0;
b [level]: = level;
level: = level-1;
end;
end;
write ('Найбільшу вагу -', max);
end.
3. Бектрекінг
Реалізувати механізм бектрекінга дуже легко. Згадаймо, що його суть в тому, щоб організувати відскік в переборі варіантів назад коли з'ясується, що йти вперед не можна. Такий відскік у нас вже є. Ось ця група операторів:
{звільняємо відділ}
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]
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_...
