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

[Zxzc]

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

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

[Zxzc]

volvo, MaxAvail в моем решении найден не верно. Говорю же "не массовое"
zZz Решение похоже на правильное... Тогда задача решается с одним массивом array[1..100,1..2] - первое число достоинство, второе - масса. В цикле вычисляем по твоей формуле и, на лету, ищем минимальное...
Отлично!