помогите определить по какому алгоритму решить задачу

суть задачи состоит в том,что:
есть 4 поля размерами 120га,95га,110га,140га..мне требуется посадить 230га ячменя..по какому алгоритму решить эту задачу,чтобы ячмень занимал как можно меньше гектаров..соответственно все числа могут меняться,Я привела лишь пример

Добавлено через 27 минут
в данном примере это будет 140+95=235..то есть всего 5га лишних засадим ячменем

0

Задача на ДП.

Сообщение от Aleksandra90 соответственно все числа могут меняться

Количество полей тоже может меняться? Какие предельно допустимые значения могут быть у входных данных?
Могу написать код на с/с++. Могу просто алгоритм.

1

да,количество полей можно выбирать,думаю 10-20 можно ограничиться смело,также можно задавать размер каждого поля(среднее поле 100га)..у каждой культуры есть своя прибыльность(есть прибыльные,есть не совем),также есть правила по которым засаживаются поля(каждая культура не может возвращаться N лет на одно поле,и после i-ой културы не может быть j-ая)..это что касается рассадки культур по полям..на выходе я хочу получить такую рассадку,при которой бы прибыльность была максимальна(пока в голове есть только вариант перебора,т.е. смотрим все поля на какие можно самую дорогую посадить,сажаем..потом дешевле и тд,но как то это не круто,хотелось бы что-нить универсальней) и плюс к этому должна быть возможность вводить ограничения,т.е. я хочу засадить обязательно 300га ячменя,150 кукурузы и при этом получить макс прибыль

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

0

Сообщение от Aleksandra90 идей нет особенно по той части,как N гектар оптимально разложить по нескольким полям,чтобы излишков было минимум,если поможете,то буду очень признательна)

По этой части я Вам сейчас алгоритм объясню.
Но условие задачи вижу немного изменилось.

Сообщение от Aleksandra90 пока в голове есть только вариант перебора,т.е. смотрим все поля на какие можно самую дорогую посадить,сажаем..потом дешевле и тд,но как то это не круто,хотелось бы что-нить универсальней

Тут Вы правы - это не самый лучший способ. Может быть вариант, когда самую дорогую культуру можно посадить на поля, при этом минимальный недосев может быть к примеру 50 га. А если выбрать немного дешевое культуру, то недосева может не быть вовсе или намного меньше 50 га, что в итоге даст более высокую прибыль.
Ладно, итак та часть которую обещал. Я на Вашем примере покажу:

Сообщение от Aleksandra90 есть 4 поля размерами 120га,95га,110га,140га..мне требуется посадить 230га ячменя..

берем массив размером 120+95+110+140=465
1 2 3 4 5 6 7 ..... 465 <-индексы массива
0 0 0 0 0 0 0 ..... 0 <-начальные значения массива
Затем такой алгоритм, перебираем числа 120, 95, 110, 140 (порядок перебора не важен) и с каждым числом делаем следующее:
- проходим по массиву от элемента с индексом 465 до элемента с индексом 1, если встречаем элемент массива равный 1 (пусть индекс этого элемента равен i), то элемент с индексом i+(очередное выбранное число) делаем равным единице. По окончании прохода массива, элемент с индексом равным очередному выбранному числу делаем равным 1.

Покажу вручную что будет получаться.
Берем очередное число 120. Проходим по массиву, элементов равных 1 нет. По окончании прохода элемент с индексом 120 равен 1.
1 2 3 4 5 6 7 .. 120 ... 465 <-индексы массива
0 0 0 0 0 0 0 .. 1 ... 0 <-значения массива
Далее берем число 95. Идем по масиву, встречаем элемент с индексом 120, делаем элемент с индексом 120+95 тоже равным 1. По окончании прохода делаем элемент с индеком 95 равным 1.
1 2 3 4 5 6 7 .. 95 .. 120 .. 215 .. 465 <-индексы массива
0 0 0 0 0 0 0 .. 1 .. 1 .. 1 .. 0 <-значения массива
Далее берем число 110, идем по массиву, встречаем 215 (делаем элемент 215+110 равным 1), встречаем 120 (делаем элемент 120+110 равным 1), встречаем 95 (делаем элемент 95+110 равным 1). По окончании прохода элемент с индексом 110 тоже равен 1.
1 2 3 4 5 6 7 .. 95 .. 110 .. 120 .. 205 .. 215 .. 230 .. 325 .. 465 <-индексы массива
0 0 0 0 0 0 0 .. 1 .. 1 .. 1 .. 1 .. 1 .. 1 .. 1 .. 0 <-значения массива
Далее берем последнее число 140. В итоге массив получится такой:
1 2 .. 95 .. 110 .. 120 .. 140 .. 205 .. 215 .. 230 .. 235 .. 260 .. 325 .. 345 .. 355 .. 370.. 465 <-индексы массива
0 0 .. 1 .. 1 .. 1 .. 1 .. 1 .. 1 .. 1 .. 1 .. 1 .. 1 .. 1 .. 1 .. 1 .. 1 <-значения массива
Кстати получается, что:

Сообщение от Aleksandra90 в данном примере это будет 140+95=235..то есть всего 5га лишних засадим ячменем

неправильно: можно набрать и ровно 230: 110+120
По окончании такого перебора всех чисел выбираем минимальное значение массива, равное 1 (от нужного значения и больше). В данном случае это 230. (Немного отвлекусь - все значения массива равные 1 - это все возможные варианты которые можно набрать)
Теперь осталось вычислить поля которыми можно набрать эту сумму.
Изначально имеем число 230.
Пока это число не станет равным 0, делаем так:
Перебираем все значения полей и если значение массива с индексом (наше число) - (значение очередного поля) равно 1, то значит это поле наше - отнимаем от (нашего числа) (значение этого поля) и продолжаем дальше.

Вот что получится: имеем 230. 230-120=110 (элемент массива с индексом 110 равен 1, поэтому это поле (120га) наше). 230-120=110 (теперь наше число 110).
Имеем 110. Перебирая числа найдем, что 110-110=0 (это тоже наше поле).

2

спасибо большое!!!сейчас буду опробывать,если что спрошу еще..еще раз огромное спасибо Вам)

0

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

0