Алгоритм поиска количества известных слагаемых

#java #c_sharp #cpp #алгоритм

Есть круг разделен на 16 секторов.Каждый сектор разделен на 10 сегментов.

В секторе 11 сегменте 7 сидит лягушка, которая прыгает: 1) прямо на 3, или на 2 прямо
и 1 в влево, или 2 прямо и 1 вправо, или на 1 прямо и 2 в влево, или на 1 прямо и 2
вправо. Она должна допригнуты до 9 сектора 10 сегмента.

Есть две елки на круге на которые она не может прыгнуть.1 елка - сектор 14 сегмент
9, 2 - сектор 5 сегмент 8.

Надо найти минимальное количество прыжков, за которые лягушка достанется в сектор
9 сегмента 10

Лягушка может прыгать только по часовой стрелке. Через центр не может. 

За круг также не может выпрыгнуть. Длина прыжка измеряется в секторах и сегментах.

Если прижок 3.0, это значит, что она прыгает на 3 сектора в перед (прямо), если 2.1
- это значит, что на 2 сектора вперед и сместилась на 1 позицию влево к краю круга
(была - 11.7 стала 13.9) .если 2. -1 то 13.6(сместилась к центру)

У меня есть пять пар чисел {3,0},{2,1},{2,-1},{1,2},{1,-2}.

Эти пары чисел можно добавлять, например,
так: 3, 0 + 2,1 = 5,1
или так: 3.0 + 3.0 + 2.1 + 1,2 = 9.3
или так: 3.0 + 2.1 + 1.2 + 2.(- 1) = 8.2.

Надо составить алгоритм, чтобы найти минимальное количество этих пар чисел (и сами
пары), сумма которых будет 14.3.
    

Ответы

Ответ 1

Упаковка рюкзака, правда в странной форме. 

Заводите двоичное число, в котором количество битов соответствует количеству ваших пар.

Затем, пишите функцию, которая будет смотреть на биты этого числа и набирать из пар
результат. Если дошли до нужного результата - ура, если превысили или так и не достигли
- увеличиваем наше двоичное число и повторяем еще раз.

Сложность брутфорса 2^N, так что если у вас не много пар - дерзайте.