Возникла проблема с поиском нескольких чисел массива сумма которых больше либо равна 1000. Первым решением было сортировать значения массива по убыванию, затем из 1000 вычесть наибольшее значение (первый элемент массива). Есть идея сравнивать результат на равенство/больше/меньше, но как поступить дальше хороших идей нет.
Примеры массивов:
800 500 100
800 201 100 100
800 500 100 110
700 600 100 100 50 50

Это сообщение отредактировал(а) okboss - 27.6.2014, 11:39

Сама задача до конца не ясна, что конкретно нужно найти? Массивы, сумма чисел которых >= 1000? Или числа из заданного массива, которые образуют такую сумму?

И что задача делает в разделе для профи? Какова аргументация помещения ее сюда?

Aliance, 

Второй вариант, извиняюсь за формулировку, задача намного обширней, поэтому пришлось сократить. 
На мой взгляд это не простая арифметическая задача

Если второй вариант, то какие именно нужны числа? Минимальные, сумма которых не меньше 1000? То есть если массив вида 500,300,200,100 - возвращаем все или без 100?

Aliance, ну допустим пусть без 100

Я немного подробнее опишу задачу, частный случай из которой привел okboss.

Возникла проблема с проверкой товаров в корзине на необходимость добавления еще одного бесплатного товара по акции. Акция срабатывает, когда сумма товаров в корзине >= 1000 руб. Соответственно, если товаров на 2000 р., то у нас в корзину падает 2 бесплатных товара по акции. И так далее...

Например, у нас в корзине:
Товар 1 - 500 р.
Товар 2 - 200 р.
Товар 3 - 500 р.
Товар 4 - 700 р.
Товар 5 - 500 р.
Товар 6 - 300 р.

Товары добавляются в корзину последовательно и ясно, что акция в данном случаем сработает по:
1) "Товар 1 - 500" + "Товар 2 - 200" + "Товар 3 - 500" = 1200. Т.е. 1200 > 1000. Все - товар по акции добавили в корзину. Эти три товара сыграли.
2) Дальше будет "Товар 4 - 700 р." + "Товар 5 - 500 р." = 1200, тоже 1200 > 1000. Добавляем еще один бесплатный товар по акции. Эти 2 товара отмечаем как создавшие акцию.
3) Остается один товар "Товар 6 - 300". 300 < 1000 - в итоге он не может создать акцию

В общем, вся эта схема некорректна, т.к. необходимо, чтобы акция включилась на товарах с наименьшей суммой:
1) "Товар 1 - 500" + "Товар 3 - 500" = 1000 == 100. Все, у нас уже достаточная сумма для акции.
2) "Товар 4 - 700" + "Товар 6 - 300" = 1000 - тоже достаточно для акции.
3) "Товар 2 - 200" + "Товар 5 - 500" = 700 - все, по этим товарам акция уже не включается.

Вот как организовать алгоритм такой работы в корзине с товарами. Здесь бы какую-нибудь математическую формулу. Потому что если городить условия, то их будет очень много. И не факт, что это будет работать надежно.

Акция включается в какой момент? В момент формирования заказа, когда товары уже сформированы и не меняются?
Если да, то

исходя из этих данных, какие товары должны формировать акции?

Нам необходимо сразу показывать покупателю, что при покупке товаров на сумму >=1000 руб. включается акция. Поэтому проверка на включение акции происходит при добавлении каждого товара в корзину.

В данном примере все товары формируют акцию, если общая их стоимость >=1000. Т.е. добавили каких-то (любых) товаров в корзину и если на сумму >=1000, то ключается акция и в корзину добавляется еще один бесплатный товар (подарок). Этот товар с нулевой ценой и при дальнейшем добавлении товаров в корзину он не будет влиять на включение акции.

Разумеется, в корзине может остаться товар или несколько товаров, которые не сформируют акцию, т.к. сумма этого товара или нескольких товаров будет <1000

Это сообщение отредактировал(а) vladimrescuer - 27.6.2014, 15:06

При добавлении товаров формировать условие проще. Как я понял есть массив со ценами товаров? Значит через array_sum у нас есть и сумма цен товаров. И можно сделать условие при добавлении вида:

Aliance, спасибо.
Но мы не можем просто последовательно складывать ценники товаров между собой. Нам нужно складывать только ценники, которые в сумме дают минимальный порог. Для нас это обязательно из-за того, что на все товары - скидка 10%, кроме тех товаров, которые формируют акцию.

В корзине:
Товар 1 - 500 р.
Товар 2 - 200 р.
Товар 3 - 500 р.
Товар 4 - 700 р.
Товар 5 - 500 р.
Товар 6 - 300 р.

Сделали акцию 1: 500+500=1000 : добавляем 1 бесплатный товар в корзину
Товар 1 - 500 р.
Товар 3 - 500 р.

А если мы сделаем так: 500+200+500 = 1200р. - И НА "ТОВАР 2" В 200 р. МЫ НЕ СМОЖЕМ ДАТЬ КЛИЕНТУ СКИДКУ, Т.К. ОН У НАС УЖЕ УЧАСТВОВАЛ В ФОРМИРОВАНИИ АКЦИИ.
Товар 1 - 500 р.
Товар 2 - 200 р.
Товар 3 - 500 р.


Потому и должны в данном примере быть сформированы акции только из товаров:
Товар 1+Товар 3
Товар 4+Товар 6
а на Товар 2 - 200 р и Товар 5 - 500 р. - МЫ ДАДИМ СКИДКУ В 10% КЛИЕНТУ. ПРИ ДРУГОМ РАСКЛАДЕ ЕМУ ДОСТАНЕТСЯ СКИДКА ТОЛЬКО НА ТОВАР 6 - 300р. Поэтому нужен первый вариант!

А в чём собственно проблема то? Если товары по акции даются только из расчёта на сумму 1000 рублей = 1 бесплатный товар по акции, то разделив сумму товара в корзине(в данном случае 2700) на 1000, и округлив 2,7 в низ, получим 2 бесплатных товара.
А дальше дело техники, если товар в корзине лежит уже совместно с товаром из акции, то складывать нужно товары без акции, а тут нужно как то различить какие товары какие. Но можно ведь товары по акции выводить на добавление в корзину уже после того как товары будут в корзине, или вообще их держать в отдельном массиве, и потом давать клиенту отметить нужные 2 товара из его 10*-и отобранных.
Может чуть сложней будет по коду с парой отдельных массивов, но меньше геморроя с поиском каких то чисел и последующими танцами с бубном над ними... ИМХО!

Этот ответ добавлен с нового Винграда - http://vingrad.com

Поскольку товаров в корзине едва ли будет 100500, можно тупо организовать перебор всех комбинаций цен:
1. Пишете функцию, последовательно считающую для некой последовательности цен количество подарков и оставшуюся сумму.
2. Организуете перебор (с рекурсией) всех порядков расположения товаров в корзине. То есть, для корзины {200, 400, 700, 800} надо просчитать функцией из п.1 следующие массивы:
{200, 400, 700, 800} 1, 800
{200, 400, 800, 700} 1, 700
{200, 700, 400, 800} 1, 800
{200, 700, 800, 400} 1, 400
{200, 800, 400, 700} 2, 0
{200, 800, 700, 400} 2, 0

{400, 200, 700, 800} 1, 800
{400, 200, 800, 700} 1, 700
{400, 700, 200, 800} 2, 0
{400, 700, 800, 200} 2, 0
{400, 800, 200, 700} 1, 900
{400, 800, 700, 200} 1, 900

{700, 400, 200, 800} 2, 0
{700, 400, 800, 200} 2, 0
{700, 200, 400, 800} 1, 800
{700, 200, 800, 400} 1, 400
{700, 800, 400, 200} 1, 600
{700, 800, 200, 400} 1, 600

{800, 400, 700, 200} 1, 900
{800, 400, 200, 700} 1, 900
{800, 700, 400, 200} 1, 600
{800, 700, 200, 400} 1, 600
{800, 200, 400, 700} 2, 0
{800, 200, 700, 400} 2, 0

(Итого, максимальное число подарков - 2, сумма неакционных твоаров - 0).

vladimrescuer, На каком этапе решается помещать или не помещать в корзину бесплатный товар?
При промотре корзины товаров? Задача очевидна. Все товары уже куплены. Сравниваем суммы цен товаров без акции, получаем количество акционых товаров, отнимаем нужное количество акционных товаров и на остальные акционные товары  навешиваем полную стоимость. Если осталась возможно докупить акционный - пишем юзеру "Забери подарок..."
В карточке товаров - как дополнительная информация к кнопке "Купить"? То же самое, но к сумме неакционых прибавляем еще цену этого товара. Дальше то же самое, если появляется еще один акционный товар - пишем - "Презент..."

Ни на каком этапе не возникает задача найти пару с бОльшей или меньшей 1000 суммой.

Это сообщение отредактировал(а) ksnk - 29.11.2015, 11:47