|
|
|
Интересная задачка.
|
|||
|---|---|---|---|
|
#18+
Mainframe_старыйон решает узкую задачу обеспечения некой суммарной сложности из некоторого набора вопросов - а уж откуда и какие это вопросы - это решаеют на основании других правил OK. В такой постановке - спасибо, понятно и недоумения не вызывает. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.08.2007, 14:49 |
|
||
|
Интересная задачка.
|
|||
|---|---|---|---|
|
#18+
softwarer MAES2 Mainframe_старый опиши алгоритм. Если не ошибаюсь, для этой задачи оптимально сработает жадный алгоритм - то есть отсортировать значения по уменьшению, а дальше идти следующим образом: - если очередное значение можно положить в первую кучку, то положить - если очередное значение можно положить во вторую кучку, то положить - ... - если очередное значение некуда класть, то начать им новую кучку - перейти к следующему Оптимально - это значит, разложит таким образом, что сумма (N - вес кучки) для всех кучек будет минимальна. Впрочем, строго доказывать (или опровергать) эту гипотезу, если честно, лениво. Что-то типа того, похоже. Я уже не помню более точно сама. Писали лет 5 назад, освежать мне тоже лениво, так как задача решена и больше неинтересна. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.08.2007, 14:50 |
|
||
|
Интересная задачка.
|
|||
|---|---|---|---|
|
#18+
Вот в принцыпе о чём я говорил: Таблтчка JO_Test(id,val,group_id) Вот алгоритм. while exists ( select val from JO_Test where ISNULL(group_id,0)=0 ) loop set @id = 0; SELECT FIRST tst.id,(select max(val) from JO_TEST where id = tst.id) as max_v into @id,@value FROM JO_TEST as tst where ISNULL(group_id,0)=0 and val < @ostatok order by val desc; if @id<>0 then update JO_TEST set group_id = @group_id where id = @id; set @ostatok = @ostatok - @value; else set @group_id = @group_id + 1; set @ostatok = @max; end if end loop; Есть замечания по оптимизации? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.08.2007, 16:19 |
|
||
|
Интересная задачка.
|
|||
|---|---|---|---|
|
#18+
MAESЕсть множество чисел. Необходимо эти числа распределить по группам. Группа представляет из себя елементы с общей сумой максимально приближенной но не более какого-то заранее определённого значения. Всё это надо сделать на SQL. Например: таблица с полями ID,VALUE,Group_ID...дальше я думаю понятно. P.S. Вот уже неделю страдаю :) Первые алгоритмы работали до 40 минут на 400 записей :) Сейчас уже 5 мин, но это очень много... Мне кажется что это напоминает известную задачу упаковки в контейнеры. Или я ошибаюсь? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.08.2007, 16:54 |
|
||
|
Интересная задачка.
|
|||
|---|---|---|---|
|
#18+
MAESЕсть замечания по оптимизации? Ээ.... а с каких пор то, что Вы написали, относится к "чистому SQL", как Вы хотели? Точнее даже MAESпошевелить мозгом. решить её скажем так в чистом SQL, без циклов и переборов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.08.2007, 16:56 |
|
||
|
Интересная задачка.
|
|||
|---|---|---|---|
|
#18+
Если бы я был уверен что имею все знания необходимые для решения этой задачи средствами SQL сервера я бы и не писал сюда. может быть я выбрал не ту тему. Да, задача про контейнеры, просто я до этого не слышал о ней. То что я написал (код выше) - это моё субъективное решение. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.08.2007, 17:12 |
|
||
|
Интересная задачка.
|
|||
|---|---|---|---|
|
#18+
SELECT MyRates.MyRate, MyArray.MyValues FROM MyArray, MyRates WHERE (((MyArray.MyValues)<[MyRates].[MyRate])) ORDER BY MyRates.MyRate; MyArray - Массив значений MyRates - Границы диапазонов запрос возвращает все диапазоны и все значения которые в них входят при заданном условии (значение < границы) может быть я не правильно понял вопрос, хотя перечел четыре раза) но ИМХО неделю думать тут не над чем ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.08.2007, 17:20 |
|
||
|
Интересная задачка.
|
|||
|---|---|---|---|
|
#18+
http://ru.wikipedia.org/wiki/Задача_об_упаковке_в_контейнеры Речь идёт об оптимальности. Проще сказать что есть например числовое множество из n элементов. Есть правило для комбинации элементов по их сумме. И цель в том чтобы сгруппировать все элементы множества так чтобы колличество групп было наименьшим. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.08.2007, 17:42 |
|
||
|
Интересная задачка.
|
|||
|---|---|---|---|
|
#18+
Интересный топик. Я думаю, что на будущее MAES себе учтет, что постановка задачи пользователем не имет ничего общего с тем, что нужно сделать на самом деле ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.08.2007, 19:56 |
|
||
|
Интересная задачка.
|
|||
|---|---|---|---|
|
#18+
kittn2Интересный топик. Я думаю, что на будущее MAES себе учтет, что постановка задачи пользователем не имет ничего общего с тем, что нужно сделать на самом деле Я и так абстрагировал как мог :) В данный момент система уже внедрена :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.03.2008, 09:59 |
|
||
|
|
start [/forum/topic.php?fid=32&msg=34751667&tid=1543986]: |
0ms |
get settings: |
9ms |
get forum list: |
12ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
165ms |
get topic data: |
12ms |
get forum data: |
3ms |
get page messages: |
66ms |
get tp. blocked users: |
2ms |
| others: | 282ms |
| total: | 555ms |
| 0 / 0 |
