задача на динамику или же перебор Опции

[Bard]

Тут у меня одна задачка которую никак не могу решить уже целую неделю. Главное не могу определиться с алгоритмом. Прошу вас помочь если сможете конечно. И так задано N чисел и требуеться найти минимальное число которое невозможно составить из сумм каких-либо заданных чисел. Но каждое заданное число можно использовать максимум один раз, т.е. можно и какое-то не использовать. Допустим если задано 1, 2, 4, 9, 100 то ответ будет 8. потому что 3 не может быть ответом так как 2+1=3, 5 тоже нет т.к. 4+1=5, и 7 т.к. 4+2+1=7, а вот 8 никак не получиться.

вот моя прога но она не совсем правильна.

var
 n,i,j:byte;
 d:array [1..100] of longint;
 cem:qword;
begin
 readln(n);
 for i:=1 to n do read(d[i]);
 if d[1]>1 then begin writeln(1); exit; end;
 i:=0;
 repeat
  inc(i); cem:=0;
  for j:=1 to i do cem:=cem+d[j];
  if cem+1<d[i+1] then begin writeln(cem+1); exit; end;
 until cem+1<d[i+1];
end.

кто нибудь знает где ошибка? может есть алгоритм получше? помогите пожалуйста.
заранее большое спасибо.

Сообщение отредактировано: Bard - 10.01.2008 20:51

[Client]

Bard, а если вводиться 1 2 9 4 100 ответ тоже должен быть 8??