Помогите составит алгоритм!!!

[iogun]

народ помогите написать прграмму на паскале.

имеются гири массой 1,2,5,7,10,20,50,70,100,200,500,... г.
дана масса тела до 1000 г. (1кг.). программа должна вычислить минимальное количество гирь с помощью которых можно уравновесить весы на одной чаше которых находится это тело. также нужно показать эти гири. гири могут находится на обеих чашах весов. одну гирю можно использовать только один раз.

например тело массой 8 г. взвешивается так:
на одной чаше тело 8 г. и гиря 2 г. на другой - гиря 10 г. 8+2=10
или
тело массой 4 г. - 4+1=5
тело массой 400 г. - 400+100=500
тело массой 308 г. 308+200+2=500+10

ХЕЛП МИ !!!! Нужно срочно!!!

[TRiPLE]

Можно попробовать суммировать от большей гири к меньшей, сравнивая результат сложения. Если больше, чем надо - отбрасываем гирю и переходим к меньшей. Если суммарная масса оставшихся гирь меньше нехватающего на чаше с гирями веса, то самую маленькую гирю стоит поставить на чашу с грузом и пробовать все заново (уже без этой гири).
Так делать до того момента, пока сумма масс гири и предмета не станет больше массы всех остальных гирь вместе взятых, либо пока не дойдешь до самой тяжелой гири. Если опять ничего не совпало, то ставишь вторую с конца гирю на постоянное место жительства к предмету на чашу, а подбираешь уже вес с поочередным добавлением второй гири к предмету (опять с конца). А если есть время, то я бы посмотрел всякие оптимизации, поскольку это уж совсем топорно. Можно считать четность какую-нибудь, применить методы оптимизированного поиска (когда массив делится пополам, потом ещё пополам и т.д., т.е. не ставить к предмету сразу меньшую гирю, а пробовать с середины), или оценивать недостающий вес при подборе гири для чаши с предметом и ставить его исходя из остатков меньших и больших гирь.
Хорошая задачка, жалко времени нету думать особо. Книжки посмотри, может есть где-нибудь что-то похожее. Должно быть.

Да, забыл. Перед тем как начать новый проход, надо пробовать отбрасывать последнюю подошедшую по весу гирю и ставить вместо неё следующую, т.е. делать откат на шаг назад и пропускать его - так пока масса оставшихся гирь опять таки не станет меньше недостающей массы для уравновешивания.

[aleks_k2]

Подозреваю нужно разложить вес предмет по степеням 10-ки,
т.е. 308= 3*100+0*10+8*1, а потом раскладывать каждую степень в отдельности. А от 1 до 10 разложить или ручками, или несложным подбором.

[TRiPLE]

Там же условие, что одну гирю можно только один раз использовать. Так бы все проще было...

[aleks_k2]

Каждый вес определяется в пределах своей степени 10-ки:
1 = 1
2 = 2
3 = 1+2
4 = 5-1
6 = 5+1
7 = 7
8 = 7+1
9 = 7+2
Поэтому дважды гири не понадобятся.

[TRiPLE]

блин, понял. чё-то я перемудрил. надо засесть за книжки. давно ничего по алгоритмам не читал. задачки порешать...

[iogun]

Aleks_k2
Спасибо попробую написать прогу.
Но на всякий случай дайте еще вариант алгоритма. Подойдет даже простой перебор. Как раз простой перебор меня больше всего и интересует - как осуществить его?

[aleks_k2]

К сожалению, то что я предложил раньше не подходит (((
Опровержением является число х=13, оно раскладывается не как 10+1+2,
а как 20-7.

Тогда еще проще. Выбирается максимальный необходимый грузик. Предлагаю следующую степень 10ки, т.е. для 3456 это будет 10000.
Получается список грузов, каждому из них нужно присвоить одит из коэф. 1, -1, 0 (т.е. груз справа, слева, не кладется вообще). Перебираются все варианты коэффициентов, это получится что-то типа
3^N, где N - кол-во грузов. Среди полученных комбинаций выбираются только подходящие, а уже среди них с минимальным количеством ненулевых коэфф.

[SL600]

не факт што оптимально... возможно и глупо но ..я б попробывал так...

Создаешь множество из гирьек которые тебе доступны...
потом на ставишь в пустую чашу гирю которая равна весу или больше веса тела..... потом заполняешь гирями чашу с телом.. что бы уровнять...
(ето если гирька на пустой чаше была больше) .. потом начинаеться суммирование гирек (выборка из 1 по n) и если сумма гирек = гирьке которая есть в множестве то берешь ее оттудаво... а из множетсва исключаешь))).. вот такой вот перебор ... пока из всех возможных сумм не будет хоть какой то что будет равна гирьке из множества.... вот и все... если гирьки все не будут разными.... значит такой вот перевес не возможен...

блин во нагнал..... проще было б прогу сделать .. чем обяснить)))..
незнаю может и поможет чем-то)))

[Hex0gen]

Согласен с aleks_k2 (самый простой алгоритм - перебором). Потребуется перебрать всего 3^N комбинаций гирь (при N = 12, это составляет около полумиллиона комбинаций).