ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачка
9 сообщений из 9, страница 1 из 1
Задачка
    #36788942
toatest2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
toatest2
Гость
Собсн есть такая задачка:
Есть коробки для инструментов и инструменты, которые можно вложить в эти
коробки. Максимальное количество мест для инструментов в коробке
ограничено, например 4-мя (тоесть в коробке может быть от одного до
четырех инструментов).
Информация о коробках для инструментов нужно хранить в таблице
реляционной БД в произвольном формате.
Каждое место для инструментов в коробке имеет ограничения по
размеру(например 4-12см.)
Необходимо обеспечить возможность наиболее оптимальным способом выбрать
с таблицы коробки, в которые можно вложить заданное количество
инструментов определенных размеров.

Пример:
К - коробка
И - количество инструментов
М - размер мест для инструментов

К И М
1 2 (2-6)(0-12)
2 3 (1-4)(0-5)(1-10)
3 3 (4-7)(1-8)(2-9)

Необходимо подобрать коробки для трех инструментов размерами: 2, 9, 6
Результат: К3.

Собсн как нужно хранить информацию о коробках и как их выбирать ?

Модератор:

Содержание сообщений
Запрещается:
# "Коверканье" слов русского языка.
...
Рейтинг: 0 / 0
12.08.2010, 16:33
| Ответить | Цитировать | Написать  
Задачка
    #36789066
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
К1 тоже подходит. Можно впихнуть 9 и 6 размер в место с размером 12.
...
Рейтинг: 0 / 0
12.08.2010, 16:58
| Ответить | Цитировать | Написать  
Задачка
    #36789219
toatest2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
toatest2
Гость
maytonК1 тоже подходит. Можно впихнуть 9 и 6 размер в место с размером 12.
В каждое место для инструментов можно вложить только один инструмент. :)
...
Рейтинг: 0 / 0
12.08.2010, 18:00
| Ответить | Цитировать | Написать  
Задачка
    #36789237
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Понятно.

А почему задаётся минимальный размер? Тоесть нельзя-ли было записать таблицу коробок так:

Код: plaintext
1.
2.
3.
4.
К И М
 1   2  ( 0 - 6 )( 0 - 12 )
 2   3  ( 0 - 4 )( 0 - 5 )( 0 - 10 )
 3   3  ( 0 - 7 )( 0 - 8 )( 0 - 9 )
?
...
Рейтинг: 0 / 0
12.08.2010, 18:07
| Ответить | Цитировать | Написать  
Задачка
    #36789265
toatest2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
toatest2
Гость
maytonПонятно.

А почему задаётся минимальный размер? Тоесть нельзя-ли было записать таблицу коробок так:

Код: plaintext
1.
2.
3.
4.
К И М
 1   2  ( 0 - 6 )( 0 - 12 )
 2   3  ( 0 - 4 )( 0 - 5 )( 0 - 10 )
 3   3  ( 0 - 7 )( 0 - 8 )( 0 - 9 )
?
Ну таово условие задачи(я ее не придумывал)...
Как вариант потому, что в местах для инструментов есть фиксаторы, и слишком маленький инструмент нельзя ими зафиксировать. Этот вариант я канешн сам домыслил :) но как говорится из песни слов не выкинешь.
...
Рейтинг: 0 / 0
12.08.2010, 18:16
| Ответить | Цитировать | Написать  
Задачка
    #36789406
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
У тебя в задании написано
Код: plaintext
1.
Информация о коробках для инструментов нужно хранить в таблице
реляционной БД в произвольном формате.
Теория говорит что списки в ячейках надо нормализовать. Т.е. создать ещё одну таблицу ячеек
CELLS и наполнить её чем-то вроде связав с таблицей коробок BOX

CELLS
idnminnmaxid_box1261201213142405251102647371838293

Количество инструментов соотв. выбросить как избыточное. Но поскольку твоя задача очень тяготеет к отображению объектов в базу и постановка поиска не совсем типичная то здесь надо отталкиваться от скорости поиска в первую очередь. Если скорость поиска по предложеной мной нормализованной модели будет достаточной то её можно оставить. Если будет тормоз и оптимизация принципиально невозможна из-за модели, то можно использовать твой вариант.
...
Рейтинг: 0 / 0
12.08.2010, 19:30
| Ответить | Цитировать | Написать  
Задачка
    #36789599
toatest2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
toatest2
Гость
Ну начинать нормализацию до решения задачи как по мне не особо правильно.
Да и зачем вообще нужна таблица с ячейками, если в условии указано что количество инструментов в ячейке строго ограничено и равно 4-м?
Как по мне, то вполне достаточно такой структуры:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
Boxes
------
Id
min_1
max_1
min_2
max_2
min_3
max_3
min_4
max_4
Вот только как из нее выбрать инструменты определенных размеров я не знаю...
Хотя, если ваша структура вам кажется более уместной, я только за. Единственное что осталось - решить поставленную задачу для такой структуры :)
...
Рейтинг: 0 / 0
12.08.2010, 22:04
| Ответить | Цитировать | Написать  
Задачка
    #36789647
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Не можешь написать SQL-запрос?

Код: plaintext
1.
2.
select * from boxes where   2  between min_1 and max2 
and  9  between min_2 and max_2 
and  6  between min  3  and max  3

Можешь еще проверять на количество если план от этого улучшается.
...
Рейтинг: 0 / 0
12.08.2010, 22:40
| Ответить | Цитировать | Написать  
Задачка
    #36790180
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
toatest2Собсн как нужно хранить информацию о коробках и как их выбирать ?
Хранить информацию о коробках в данной постановке задачи вообще не нужно :) Важна только информация о местах:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
create table place (
  place_id integer not null primary key,
  box_id integer not null, -- коробка
  box_order integer not null, -- место в коробке
  size_min integer not null, 
  size_max integer not null, -- диапазон размеров
  constraint place_uk unique (box_id, box_order), -- каждое место только раз
  constraint place_cnt_chk check (box_order in ( 1 ,  2 ,  3 ,  4 )), -- в коробке не более 4-х мест
  constraint place_size_chk check (size_min <= size_max) -- диапазон существует
)

А вот как подбирать - это интересный вопрос, расписываемый в толстых книгах. Читайте по словам "задача о рюкзаке", "жадные алгоритмы", "динамическое программирование".
...
Рейтинг: 0 / 0
13.08.2010, 11:12
| Ответить | Цитировать | Написать  
9 сообщений из 9, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачка
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=36788942&tid=1343524]:
 0ms
get settings:
 5ms
get forum list:
 10ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 173ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 28ms
get tp. blocked users:
 1ms
others: 197ms
total:  427ms
созд. / загр.: 427ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]