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

[Zxzc]

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

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

[Zxzc]

, рекурсия не причем.
Вот моё, абсолютно не массовое, решение:
Пусть имеются три вида монет массами m1, m2 и m3 и достоинством d1,d2,d3.
MaxAvail - "максимальное число переборов" - найдем по формуле (P/Вес самой дешевой).
P - вес монет, S - стоимость товара.
Тогда все сводится к

For i:=1 to MaxAvail do
 For j:=1 to MaxAvail do
  For k:=1 to MaxAvail do
   If m1*i+m2*j+m3*k = P then
    If d1**i+d2*j+d3*k<S then 
     begin
      Write('Может не хватить!');
       readln;
       exit;       
     end;
Write('Разбивай');
end.

Но это решение не верно т.к.
1. Число разновидностей не известно заранее.
2. Если бы меньшей монете соответствовал меньший вес, то задача решалась бы в 2 строчки:

If P/Massa_min>S/Dostoinstvo_min then Write('Может не хватить!')
Else Write('Разбивай');

Может мы что-то сможем получить, развивая второе рассуждение...

P.S. На дискете у меня есть 2 варианта решения препода. Но вот незадача: "DISK NOT FORMATED. DO YOU WANT FORMAT IT NOW?" Если у меня получится таки достать файлы с исходниками я сразу же их выложу. А иначе до конца выходных...