Привет.
Наткнулся тут на одну интересную задачу.

Предприятие "Витязь" торгует рубероидом одной марки. Рубероид поступает в рулонах различной длины. Учет товара ведется на счете 41, на котором предусмотрен аналитический и количественный учет по товарам. Каждый товар имеет следующие обязательные характеристики: Код, наименование, длина рулона, отпускная цена рулона.

Отпуск товара осуществляется по заказам покупателей только целыми рулонами. Количество отпускаемого товара запрашивается покупателем в метрах.

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

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

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

Пример

По данным учета текущие запасы товара "Рубероид РБ22" составляют:

Метраж рулона    Кол-во рулонов    Отпускная цена
27                                    12           270
45                                    11           450
60                                     0           600
22                                    17           220
47                                    9           470

Покупатель ООО "Фабрика грез" затребовал 260 м. товара "Рубероид РБ22".
На основании данного требования программа сформировала следующий счет.

Наименование    Метраж рулона    Кол-во рулонов    Метров    Сумма
Рубероид РБ22             27                           8                    216     2160

Рубероид РБ22             22                        2                     44        440

Итого        
    
Метров: 260
Сумма: 2600


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

1. Выбираем наименьший метраж рулона.
    Это сделано для того, чтобы в случае когда невозможно подобрать нужное количество метров рубероида, разница была минимальной так-как берем рулоны с     наименьшим метражем. 
2. Сам алгоритм:

Строим некоторое подобие массива.

Массив 1:
22*1=22
22*2=44
22*3=66
22*4=88
22*5=110
22*6=132
22*7=154
22*8=176
22*9=198

Массив 2:
27*1=27
27*2=54
27*3=81
27*4=108
27*5=135
27*6=162
27*7=189
27*8=216
27*9=243
27*10=270
27*11=297
27*12=324

и т.д.

Теперь берем нулевой элемент первого массива и складываем его с нулевым элементом второго массива.
Если 260 не получилось идем далее, складываем нулевой элемент первого массива с первым элементом второго массива.
Если 260 не получилось идем далее...

Если поочередно при сложении нулевого элемента первого массива с элементами второго массива неполучилось 260 то проделываем те-же функции только с первым элементом первого массива:

Берем первый элемент первого массива и складываем его с нулевым элементом второго массива.
Если 260 не получилось идем далее, складываем первый элемент первого массива с первым элементом второго массива.
Если 260 не получилось идем далее...

В итого когда мы сложим первый элемент первого массива с восьмым элементом второго массива, то получим 260.

Недостаток метода   в том, что сравниваются только два метража рубероида.
Ну и сам метод конечно   

У кого есть какие идеи!?

Это сообщение отредактировал(а) Deo - 15.4.2010, 08:53

Почитайте про "задачу о рюкзаке" и не изобретайте велосипедов.