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

[Zxzc]

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

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

[Zxzc]

Я понял ход твоих мыслей! Т.е. если не будет найдено соответствия - масса введена не верно...

P.S.Моя фраза об обязательной минимальности резульата на самом деле нуждается в доказательстве. Я уверен в этом довольно сильно, но руку на отсечение пока не дам... Кто это докажет/опровергнет?

Это выглядит довольно правдоподобно, но с доказательством труднее. Я сделал несколько набросков доказательства, но пока ничего не выходит.
Вчера предложил эту задачу одногрупнику, и если я - лучший в группе, то он из отстающих. За 20 секунд он решил задачу методом zZz, еще через 10 столкнулся с проблемой... Я, конечно, описывал ему задачу в упрощенном варианте, но все-таки...где после этого логика и справедливость? Наверное я загнался... Выспаться бы...

[Lapp]

> Я понял ход твоих мыслей!
> Т.е. если не будет найдено соответствия - масса введена не верно...
Именно так. Не все массы можно скомбинировать из монет. Например, масса 1 в моем наборе не получится никогда..

> Это выглядит довольно правдоподобно, но с доказательством труднее.
> Я сделал несколько набросков доказательства, но пока ничего не выходит.
А нужно ли здесь строгое доказательство? Это же не комбинаторика, а программирование..
Нет, я не имею в виду, что допустимы неверные решения, но строгость доказательства... кхм..
Ладно, я попробую сделать доказательство, если нужно..

Глюков в моей проге пока не заметил?

Сообщение отредактировано: lapp - 12.05.2006 6:42