Интересная задачка :)

[-FIXER-]

Здравствуйте. Столкнулся с проблемой и котелок не может придумать решение. Хочу подключить коллективный мозг. Для упрощения понимания придумаю гипотетический пример. Суть следующая:

Предположим, у нас есть некий магазин в котором нужно купить определённый товар, который стоит (X) долларов. Х - это переменная и каждый раз её значение меняется. Ну для примера возьмём за X сумму в $117.47. Но самих денег у нас нет, а оплачиваем мы акциями(или, если хотите, марками, или фантиками). Суть в том, что акции/марки/фантики стоят тоже по-разному. Допустим, акции у нас разных фирм и каждая акция стоит по-своему. Цена может колебаться от $0.5 до $200 за штуку. И задача состоит в том, чтобы набрать акций на сумму ровно $117.47, если это возможно, а если невозможно, то на максимально близкую сумму к нашему (X), но не меньше. Т.е. можно набрать акций на $117.47, на $117.48, $117.49, $117.50. Если разница больше, чем в 4 цента, то это уже критично.

Для примера вот массив с ценами наших акций: [0.67, 0.84, 0.86, 0.86, 0.89, 1.7, 1.8, 1.87, 1.99, 2, 2.01, 2.06, 2.09, 2.85, 2.88, 2.99, 3.14, 3.17, 4.45, 4.49, 5.01, 5.76, 5.78, 8.91, 9, 12.54, 17.83, 54.11, 77.12, 103.3, 140.88]
У меня в голову только дуратские варианты лезут. Может у кого-нибудь есть более-менее деликатные варианты. Важно чтобы это было не очень ресурсозатратно и времязатратно, в случае если массив цен акций содержит большое количество элементов. Обычно это не больше 300 элементов.

[j0hnik]

1п. берем последнюю ячейку массива, если она больше стоимости меняем ее на предпоследнюю и так далее.. пока не дойдем до меньшей или до наиболее минимально возможной.
2п. если последняя ячейка не больше стоимоти, то сохраняем ее в переменную и к ней будем плюсовать следующую по тому же алгоритму что и первом пункте.

[j0hnik]

чтобы максимально точно попасть в стоимость нужно будет использовать какой то более сложный алгоритм. это уже вопрос больше к математикам.

[-FIXER-]

1п. берем последнюю ячейку массива, если она больше стоимости меняем ее на предпоследнюю и так далее.. пока не дойдем до меньшей или до наиболее минимально возможной.
2п. если последняя ячейка не больше стоимоти, то сохраняем ее в переменную и к ней будем плюсовать следующую по тому же алгоритму что и первом пункте.

Спасибо за ответ, но Ваш вариант не подходит. На самом деле у меня в голове этот вариант изначально возник, но он не позволит максимально приблизиться к необходимой сумме. Разница может достигать высоких значений (пол доллара или доллар), а максимально допустимая разница - 4 цента.

[laimas]

Т.е. можно набрать акций на $117.47, на $117.48, $117.49, $117.50. Если разница больше, чем в 4 цента, то это уже критично.

Тогда почему разрешен выбор 140.88? Или для указанного диапазона цен акций есть некий критерий на который можно набрать, и если да, то как он определяется?

[рони]

-FIXER-,
так?

alert(2*54.11 +0.84 * 10 + 1 * 0.86)

[j0hnik]

alert(2*54.11 +0.84 * 10 + 1 * 0.86)

Так, только алгоритм нужен, для любых чисел я так понял

[рони]

alert(2.06 * 49 + 5.76 * 2 + 5.01)//117.47

[j0hnik]

alert(2.06 * 49 + 5.76 * 2 + 5.01)//117.47

вручную подбирал?

[рони]

вручную подбирал?

да