58 lines
1.4 KiB
ObjectPascal
58 lines
1.4 KiB
ObjectPascal
// Задача о ранце. В массиве B заданы веса предметов.
|
||
// Выдать все варианты полной комплектации ранца частью этих предметов
|
||
const Sz=100;
|
||
|
||
type IntArr = array [1..Sz] of integer;
|
||
|
||
procedure PrintArr(const A: IntArr; n: integer);
|
||
begin
|
||
for var i:=1 to n do
|
||
Print(A[i]);
|
||
Println;
|
||
end;
|
||
|
||
procedure TrySolve(n: integer; const B: IntArr; nb: integer);
|
||
var
|
||
Subset: IntArr;
|
||
space: integer;
|
||
ns: integer;
|
||
|
||
procedure TrySolve0(i: integer);
|
||
begin
|
||
if space=0 then
|
||
PrintArr(Subset,ns)
|
||
else if (space<0) or (i>nb) then
|
||
exit // отсечение
|
||
else // продолжение перебора всех подмножеств множества B
|
||
begin
|
||
TrySolve0(i+1); // попробовать не взять i-тый элемент
|
||
|
||
ns += 1;
|
||
Subset[ns] := B[i];
|
||
space := space - B[i];
|
||
TrySolve0(i+1); // попробовать взять i-тый элемент
|
||
space := space + B[i];
|
||
ns -= 1;
|
||
end;
|
||
end;
|
||
|
||
begin
|
||
space:=n;
|
||
TrySolve0(1);
|
||
end;
|
||
|
||
procedure FillArr(var B: IntArr; var n: integer);
|
||
begin
|
||
n:=5; // количество предметов
|
||
B[1]:=8; B[2]:=5; B[3]:=13; B[4]:=3; B[5]:=15; // веса предметов
|
||
end;
|
||
|
||
var
|
||
B: IntArr;
|
||
nb: integer;
|
||
|
||
begin
|
||
FillArr(B,nb);
|
||
TrySolve(23,B,5);
|
||
end.
|