powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Подскажите алгоритм решения задачи.
11 сообщений из 11, страница 1 из 1
Подскажите алгоритм решения задачи.
    #36893003
Aztech
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Дано: Есть множество элементов (реально порядка 400-500). Их значения лежат в диапазоне от 0,1 до 10.
Нужно распределить их в группы так, чтобы сумма их значений не превышала 10, а количество таких групп было бы минимальным.
Потом все это надо будет реализовать в VBA на Access, но главное сейчас - это алгоритм, ничего, кроме тупого перебора пока в голову не лезет. Заранее спасибо!
...
Рейтинг: 0 / 0
Подскажите алгоритм решения задачи.
    #36893997
nosov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Найти : количество групп в которых сумма чисел не превышает 10

имхо
расположите все числа в случайном порядке
разделите этот ряд на две группы
посчитайте сумму в каждой группе
если она больше 10 разбейте каждую группу на две
посчитайте сумму в каждой группе
и тд
...
Рейтинг: 0 / 0
Подскажите алгоритм решения задачи.
    #36894033
Volochkova
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
цикл до победы.

1:
Сортируем всех по убыванию.
если ничего нет, то выход

В группу кидаем первый элемент
сумма группы = сумма группы + элемент.

2:
теперь берем все элементы которые меньше чем (10 - сумма группы) сортируем по убыванию
если элементов нет, то новая группа (сумма группы = 0 и номер группы ++) go 1:
если есть
В группу кидаем первый элемент
сумма группы = сумма группы + элемент.
Go 2:


конец цикла.

как то так
...
Рейтинг: 0 / 0
Подскажите алгоритм решения задачи.
    #36894213
Фотография ПЕНСИОНЕРКА
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aztech,

для упрощение -ексель
1столб-случайный на 975 строк,494-сумма ячеек
2столб получен из первого (без формул) -для отладки
3столб абсолют(2столб-половина лимита) для сортировки

остальное в программе

результат 512 групп на 494=1,03

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
Sub mm()
j1a =  0 
j2 =  1 
s2a =  0 
Range("e1:f977").Value =  0 
Do While j1a <  975 
s1 =  0 
j1 =  0 
    Do While j1 <  975 
    j1 = j1 +  1 
    s2 = s1 + Excel.ActiveSheet.Cells(j1,  2 )
    If s2 <=  100  And Excel.ActiveSheet.Cells(j1,  6 ) =  0  Then
    s1 = s2
    Debug.Print Excel.ActiveSheet.Cells(j1,  2 );
    Excel.ActiveSheet.Cells(j1,  5 ) = s1
    Excel.ActiveSheet.Cells(j1,  6 ) = j2
    End If
    Loop
    
j1a = j1a +  1 
If s1 >  0  Then
j2 = j2 +  1 
s2a = s2a + s1
Debug.Print j2, s1, s2a, s2a \  100 
End If
Loop
End Sub
...
Рейтинг: 0 / 0
Подскажите алгоритм решения задачи.
    #36894852
Aztech
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Volochkova,

Если я правильно понял, то не оптимально... К примеру ряд {6,5,3,2,2,2} объективно оптимально разбивается на {6,2,2} и {5,3,2}, а по указанному алгоритму получается {6,3},{5,2,2},{2}. Но все равно спасибо!
...
Рейтинг: 0 / 0
Подскажите алгоритм решения задачи.
    #36895465
Valer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Переведите ваши числа в целые числа.
После этого задача будет называться задача о рюкзаке .
Можете поискать программы с названием линейный раскрой ,
в том числе и бесплатные.
полный перебор на 400 - 500 элементов - замучаетесь ждать результат.
то что предлагали предыдущие авторы не дает оптимальный результат
...
Рейтинг: 0 / 0
Подскажите алгоритм решения задачи.
    #36897525
Aztech
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Valer,

Ну рюкзак не совсем то, а вот линейный раскрой по сути решения - самое то! Теперь найти бы алгоритмы. Начинаю читать литературу 80х годов про оптимизацию раскроя материалов (трубы, листы металла...). Жесть...
...
Рейтинг: 0 / 0
Подскажите алгоритм решения задачи.
    #36898662
Valer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
aztech

посмотрите почту на mail.ru
...
Рейтинг: 0 / 0
Подскажите алгоритм решения задачи.
    #36899243
Aztech
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Valer,

Посмотрел. ЗдОрово! Вот только мне бы исходники или описание алгоритма. Мне этот модуль нужно будет внедрять в БД, которая будет взаимодействовать с внешними источниками данных. Хотя понимаю,что это интеллектуальная собственность...

PS: Так в итоге в основе обработки лежит задача о рюкзаке?
...
Рейтинг: 0 / 0
Подскажите алгоритм решения задачи.
    #36899264
joker 79
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Случайно заглянул... заинтересовало... и, на всякий случай, подкину то, что я нашел:

Собсна эта задача - "Задача об упаковке в контейнеры"

Вот тут маленькое обоснование, алгоритмы и даже онлайн-калькулятор
http://www.planetcalc.ru/917/
...
Рейтинг: 0 / 0
Подскажите алгоритм решения задачи.
    #36901811
Valer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
да
...
Рейтинг: 0 / 0
11 сообщений из 11, страница 1 из 1
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Подскажите алгоритм решения задачи.
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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