Задача о вероятности, Задача полностью решена Опции

[Zxzc]

Помогите решить задачу:
Мальчик накапливал в копилке деньги. Однажды он увидел в магазине некий товар стоимостью S.
Дело в том что копилка заполнена не до конца, а разбивать ее можно лишь при 100% уверенности,
что количества денег будет достаточно. Но он не помнит сколько монет какого достоинства клал в копилку. Также известна масса пустой копилки и, конечно, текущая масса.
Известны соотношения Номинал <--> Масса монеты. Нужно определить минимальную вероятность и если она равна 100% вывести:"Вперед!!!!!!!!!!!"
Я решил задачу, получилось что количество вложенных циклов равно количеству разновидностей монет.
Проблема в том, что заранее не известно число разновидностей
монет. Также важно, что монеты, номинал которых больше, не всегда тяжелее. Но это не проблема...
Препод предложил идти через двумерный массив(M,N его - большие числа). И каким-то замысловатым способом из 2-х массивов(в первом - номиналы, во втором - массы) получаем массив [m,n]-й элемент к-рого - минимальное кол-во денег... Потом он сам запутался...
Мда.. Давно я так не попадался...

Сообщение отредактировано: Zxzc - 13.05.2006 21:44

[Zxzc]

Внимание! Я достал-таки исходники!
1:

const Len=100;
var e,f,n,i,j:integer;
    P, W:array[1..Len] of integer;
    D:array[0..Len, 0..Len] of integer;
function min(a,b:integer):integer;
 begin
  if (a<b) then min:=a else min:=b;
  if (b<0) then min:=a;
 end;
begin
 writeln('‚ўҐвЁвҐ ўҐб Їгбв®© Ё Ї®«­®© Є®ЇЁ«ЄЁ зҐаҐ§ Їа®ЎҐ«');
 readln(e, f); f:=f-e;
 writeln('‚ўҐ¤ЁвҐ Є®«ЁзҐбвў®вЁЇ®ў ¬®­Ґв');
 readln(n);
 writeln('‚ўҐ¤ЁвҐ ¤®бв®Ё­бвў® Ё ўҐб ¬®­Ґв зҐаҐ§ Їа®ЎҐ«');
 for i:=1 to n do
  begin
   write(i,' ¬®­Ґвл: ');
   readln(P[i], W[i]);
  end;
 for i:=0 to n do
  for j:=1 to f do
    D[j, i]:=maxint;

 for i:=1 to n do
  for j:=W[i] to f do
   D[j, i]:=min(D[j,i-1], D[j-W[i],i]+P[i]);

 for j:=1 to f do
  begin
   for i:=1 to n do
    write(D[j, i]:5,' ');
   writeln;
  end;
 writeln('ЊЁ­Ё¬ «м­ п б㬬  а ў­ : ',D[f, n],' ',f);
 readln;
end.

В чем суть этого решения?

Это,(

var e,f,n,i,j:integer;
    m:longint;
    P, W:array[1..500] of integer;
    d:array[0..10000] of longint;

begin
 writeln('‚ўҐвЁвҐ ўҐб Їгбв®© Ё Ї®«­®© Є®ЇЁ«ЄЁ зҐаҐ§ Їа®ЎҐ«');
 readln(e, f); f:=f-e;
 writeln('‚ўҐ¤ЁвҐ Є®«ЁзҐбвў®вЁЇ®ў ¬®­Ґв');
 readln(n);
 writeln('‚ўҐ¤ЁвҐ ¤®бв®Ё­бвў® Ё ўҐб ¬®­Ґв зҐаҐ§ Їа®ЎҐ«');
 for i:=1 to n do
  begin
   write(i,' ¬®­Ґвл: ');
   readln(P[i], W[i]);
  end;
 D[0]:=0; for i:=1 to f do D[i]:=maxlongint;
 for i:=1 to n do
  begin
   j:=W[i];
   while j<=f do
    begin
     m:=D[j-W[i]];
     if m<maxlongint then m:=m+P[i];
     if m<D[j] then D[j]:=m;
     j:=j+1;
    end;
  end;
 if D[f]=maxlongint then writeln('No')
 else writeln('ЊЁ­Ё¬ «м­ п б㬬  а ў­ : ',D[f]);
 readln;
end.

) решение являлется усовершенствованной версией предыдущего, более оптимальное, но и более запутанное.