Из камней весом рₐ (а=1,...,N) требуется набрать кучу весом ровно W или, если это невозможно, максимально близкую к W (но меньшую, чем W). Все веса камней и значение W - целые числа. Программа на языке pascal.

Предыдущий
вопрос Следующий
вопрос

program StonePile;
const
N = 10;
var
stones: array [1..N] of integer;
W, totalWeight, closestWeight: integer;
i, j: integer;
dp: array [0..N, 0..1000] of boolean;
procedure findClosestWeight;
begin
closestWeight := 0;
for i := 1 to N do begin
for j := totalWeight div 2 downto 1 do begin
if dp[i-1, j] then begin
dp[i, j+stones[i]] := true;
dp[i, j] := true;
if (j+stones[i] > closestWeight) and (j+stones[i] <= W) then
closestWeight := j + stones[i];
end;
end;
end;
end;
begin
// Ввод весов камней
for i := 1 to N do
readln(stones[i]);
// Ввод необходимого веса
readln(W);
// Инициализация двумерного массива для динамического программирования
totalWeight := 0;
for i := 1 to N do
totalWeight := totalWeight + stones[i];
fillchar(dp, sizeof(dp), false);
dp[0, 0] := true;
findClosestWeight;
// Вывод результата
if closestWeight = W then
writeln('Можно набрать кучу весом равно W')
else if closestWeight > 0 then
writeln('Можно набрать кучу весом ', closestWeight)
else
writeln('Невозможно набрать кучу весом W');
end.