INFOMAN брой 15
{ This is the input data: N; P1; p2; pN...
11
3
1
100
301
400
300
50
100
202
48
1
1 КИЛОГРАМ ПЛОДОВЕ
------------------
Национална олимпиада по информатика,
Финален (4-ти, подборен) кръг, 1999 г.
Условие на задачата. Дадени са теглата на N плода в грамове. Пита се
може ли да се изберат някои от тези плодове, така че общото тегло на из-
браните плодове да е точно 1 килограм. Входните данни са числото N <= 50
и теглата W[1,2,...N] на всеки плод (W[1,2,...N] <=1000) всичко на отдел-
ни редове. Ако може да се получи 1 килограм (1000 грама) да се отпечатат
теглата на избраните плодове (на отделни редове всяко) или "NO" ако няма
решение.
РЕШЕНИЕ
-------
Ще решим задачата с динамично оптимиране.
Нека Can[k,KG] = true ако съществува подмножество на първите k плода,
което тежи KG килограма. Тогава Can[k,KG] можем да изчислим по формулите:
Can[0,0] = true
Can[k,KG] = true
ако Can[k-1,KG-W[k]] (взимаме k-тия плод)
или ако Can[k-1,KG] = true (пропускаме k-тия плод)
иначе Can[k,KG] = false
В задачата търсим Can[N,1000].
Тези формули изразяват следното: От първите K плода можем да изберем под-
множество, което има сумарна тежест KG само в два случая:
- ако в това подмножество участва плода с номер k и от първите k-1 пло-
да можем да изберем подмножество, което има сумарна тежест KG-W[i].
- ако в това подмножество не участва плода с номер k и от първите k-1
плода можем да изберем подмножество, което има същата сумарна тежест KG.
За да можем не само да проверим дали можем да получим точно 1000 гра-
ма плодове е необходимо да изчислим и още една таблица освен таблицата
Can[0..N,0..1000]. Тази таблица Take[k,KG] показва дали плодът с номер k
участва в подмножеството на първите k предмета със сума KG. Тази таблица
можем да изчислим по време на изчислението на таблицата Can. Въпреки че
формулата дадена по-горе е рекурсивна, ние можем да я изчислим по итера-
тивен начин като започнем с Can[0][1..1000], продължим с Can[1][0..1000],
с Can[1][0..1000] и т.н. до Can[N][0..1000]. Алгоритъмът е следният:
Can[0...N][0...1000] = false;
Take[0...N][0...1000] = false;
Can[0,0] = true;
за k = 1 ... N изпълнявай // изчисляваме за първите k плода
Can[k][0...1000] = Can[k-1][0...1000];
за weight = W[k] ... KG изпълнявай // изчисляваме за тежест weight
ако Can[k-1][weight-W[k]] then // взимаме плода K
Can[k][weight] = true;
Take[k][weight] = true;
Алгоритъмът за намиране на плодовете със сумарна тежест 1000 е:
KG = 1000;
ако Can[N,KG] = false, няма решение
иначе изпълни
повтаряй
ако Take[N]^[KG] изпълни
KG = Kg - W[N]; отпечатай W[N] // плодът N участва
N = N-1
докато N = 0;
Хубавото на посочения алгоритъм за решаване на задачата е че използва памет
от порядъка на M*N*2 бита, което е всъщност M*N/4 байта, където M е макси-
малната сумарна тежест (1000), а N е броя предмети. Сложността на алгоритъ-
ма е от порядъка на O(N*M).
Светлин Наков
септември, 1999
}
CONST InFileName = 'FRUITS.PAS';
OutFileName = '';
MaxN = 50;
MaxKG = 1000;
KG: word = 1000;
TYPE TRow = array[0..MaxKG] of boolean;
VAR N: integer;
W: array[1..MaxN] of integer;
Can,Take: array[0..MaxN] of ^TRow;
Procedure ReadData; { Read the input data - N and W[1..N] }
Var F: Text;
Begin
Assign(F,InFileName); Reset(F); ReadLn(F);
ReadLn(F,N);
for N:= 1 to N do
ReadLn(F,W[N]);
Close(F);
End;
Procedure CalculateF;
Var k,weight: integer;
Begin
for k:= 0 to N do
begin
New(Can[k]); FillChar(Can[k]^,SizeOf(Can[k]^),false);
New(Take[k]); FillChar(Take[k]^,SizeOf(Take[k]^),false);
end;
Can[0]^[0]:=true;
for k:= 1 to N do
begin { Изчисляваме всички възможни суми от тегла за първите K плода }
Can[k]^:= Can[k-1]^;
for weight:= W[k] to KG do
if Can[k-1]^[weight-W[k]] then
begin { взимаме плода K }
Can[k]^[weight]:= true;
Take[k]^[weight]:= true;
end;
end;
End;
Procedure PrintSolution;
Var OutF: Text;
i: integer;
Procedure PrintFruits;
Var i: integer;
Begin
repeat
if Take[N]^[KG] then
begin Dec(KG,W[N]); WriteLn(OutF,W[N]); end;
Dec(N);
until N = 0;
Close(OutF); Halt;
End;
Begin
Assign(OutF,OutFileName); Rewrite(OutF);
if Can[N]^[KG] then
PrintFruits
else WriteLn(OutF,'NO');
Close(OutF);
End;
BEGIN
ReadData;
CalculateF;
PrintSolution;
END.