Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/9: Рейтинг темы: голосов - 9, средняя оценка - 5.00
99 / 98 / 11
Регистрация: 12.09.2016
Сообщений: 195

Разделить N контейнеров на Q примерно равных долей

20.05.2019, 15:38. Показов 1873. Ответов 8
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Дано N контейнеров весом a1,a2,a3..an. Нужно распределить эти контейнеры между Q транспортными средствами так, чтобы итоговая масса груза во всех транспортных средствах была примерно одинаковой

У меня была задумка, которая заключалась в том, чтобы изначально в каждое тс класть контейнер с минимальной массой, а потом "закидывать" туда контейнер с весом максимально приближенным к разнице среднего веса всех контейнеров и текущей массой тс, но идея провалилась
1
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
20.05.2019, 15:38
Ответы с готовыми решениями:

Разделить массив на два примерно равных массива
Вот я сделал массив, как потребовали #include <iostream> #include <limits> #include <ctime> using namespace std; int main() { ...

Разделить массив на два примерно равных массива
Помогите написать код на с++ для программы Она должна делить массив на 2 подмассива что равны друг другу(или примерно) П.5.4. Правил ...

Представить целое число N в виде суммы M примерно равных целых чисел.
В голове не приходит нормального решения. Именуйте темы осмысленно! Название темы должно максимально полно отражать её содержимое.

8
 Аватар для SomniPhobia
602 / 439 / 137
Регистрация: 22.11.2017
Сообщений: 1,405
20.05.2019, 17:23
Gaveyn, привет!
У меня такая идея. Я использовал принцип работы с рычажными весами в лаборатории -> про правила добавление гирек на чашу, чтобы узнать массу груза на другой чаше. На его основе построил следующий алгоритм.
Спасибо, интересная задача.

Кликните здесь для просмотра всего текста

C++
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
 
using namespace std;
 
int main()
{
    setlocale(LC_ALL, "Rus");
    
    //Получение и сохранение исходных данных
    cout << "Укажите количество транспортных средств Q = ";
    size_t q;
    cin >> q;
    cout << "Вводите массы контейнеров. Для завршения ввода укажите не число" << endl;
    istream_iterator<double> start{ cin };
    istream_iterator<double> finish;
    vector<double> box;
    copy(start, finish, back_inserter(box));
 
    //Расчёт
    sort(begin(box), end(box), greater<double>());
    vector<double> means_transport;
    if (box.size() < q)
    {
        means_transport.resize(box.size());
        copy(cbegin(box), cend(box), begin(means_transport));
    }
    else
    {
        means_transport.resize(q);
        auto hook = begin(box);
        advance(hook, q);
        copy(begin(box), hook, begin(means_transport));
        box.erase(begin(box), hook);
        for (const auto& value : box)
        {
            auto it_min = min_element(begin(means_transport), end(means_transport));
            *it_min += value;
        }
    }
 
    //Вывод результата
    cout << "Результат разделения грузов по транспортным средствам" << endl;
    copy(cbegin(means_transport), cend(means_transport), ostream_iterator<double>(cout, " "));
 
    return 0;
}
Миниатюры
Разделить N контейнеров на Q примерно равных долей  
1
 Аватар для SomniPhobia
602 / 439 / 137
Регистрация: 22.11.2017
Сообщений: 1,405
20.05.2019, 17:31
Вот ещё скрины работы программы.
Миниатюры
Разделить N контейнеров на Q примерно равных долей   Разделить N контейнеров на Q примерно равных долей   Разделить N контейнеров на Q примерно равных долей  

1
 Аватар для SomniPhobia
602 / 439 / 137
Регистрация: 22.11.2017
Сообщений: 1,405
20.05.2019, 18:05
Добавил детализацию: Какая машина какой массы грузы повезёт.

Кликните здесь для просмотра всего текста

C++
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
 
using namespace std;
 
int main()
{
    setlocale(LC_ALL, "Rus");
    
    //Получение и сохранение исходных данных
    cout << "Укажите количество транспортных средств Q = ";
    size_t q;
    cin >> q;
    cout << "Вводите массы контейнеров. Для завршения ввода укажите не число" << endl;
    istream_iterator<double> start{ cin };
    istream_iterator<double> finish;
    vector<double> box;
    copy(start, finish, back_inserter(box));
    cout << endl;
 
    //Расчёт и вывод результата
    sort(begin(box), end(box), greater<double>());
    vector<double> means_transport;
    cout << "Результат разделения грузов по транспортным средствам" << endl;
    if (box.size() < q)
    {
        means_transport.resize(box.size());
        copy(cbegin(box), cend(box), begin(means_transport));
        for (size_t scroll = 0u; scroll < means_transport.size(); ++scroll)
        {
            cout << "ТС №" << scroll + 1 << " повезёт груз массой " << means_transport[scroll] << endl;
        }
    }
    else
    {
        means_transport.resize(q);
        auto hook = begin(box);
        advance(hook, q);
        copy(begin(box), hook, begin(means_transport));
        vector<vector<double>> statist(q);
        size_t idx = 0u;
        for (auto it = begin(box); it != hook; ++it)
        {
            statist[idx++].push_back(*it);
        }
        box.erase(begin(box), hook);
        for (const auto& value : box)
        {
            auto it_min = min_element(begin(means_transport), end(means_transport));
            *it_min += value;
            statist[distance(begin(means_transport), it_min)].push_back(value);
        }
        for (size_t scroll = 0u; scroll < statist.size(); ++scroll)
        {
            cout << "ТС №" << scroll + 1 << " повезёт груз массой " << means_transport[scroll] << " <- ";
            auto ts = statist[scroll];
            for (size_t u = 0u; u < ts.size(); ++u)
            {
                cout << ts[u] << (u == ts.size() - 1 ? "\n" : " + ");
            }
        }
    }
 
    return 0;
}
Миниатюры
Разделить N контейнеров на Q примерно равных долей  
2
 Аватар для SomniPhobia
602 / 439 / 137
Регистрация: 22.11.2017
Сообщений: 1,405
20.05.2019, 19:09
Gaveyn, оптимизировал и причесал код.

Кликните здесь для просмотра всего текста

C++
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
 
using namespace std;
 
int main()
{
    setlocale(LC_ALL, "Rus");
    
    //Получение и сохранение исходных данных
    cout << "Укажите количество транспортных средств Q = ";
    size_t q;
    cin >> q;
    cout << "Вводите массы контейнеров. Для завршения ввода укажите не число" << endl;
    istream_iterator<double> start{ cin };
    istream_iterator<double> finish;
    vector<double> boxes;
    copy(start, finish, back_inserter(boxes));
    cout << endl;
 
    //Расчёт
    sort(begin(boxes), end(boxes), greater<double>());
    vector<double> transport_total_mass(q);
    vector<vector<double>> distribution(q);
    for (auto mass_box : boxes)
    {
        auto it_min = min_element(begin(transport_total_mass), end(transport_total_mass));
        *it_min += mass_box;
        distribution[distance(begin(transport_total_mass), it_min)].push_back(mass_box);
    }
 
    //Вывод результата
    cout << "Результат разделения грузов по транспортным средствам" << endl;
    for (size_t idx_ts = 0u; idx_ts < distribution.size(); ++idx_ts)
    {
        cout << "ТС №" << idx_ts + 1 << " повезёт груз массой " << transport_total_mass[idx_ts] << " <- ";
        auto transport_boxes = distribution[idx_ts];
        auto transport_boxes_count = transport_boxes.size();
        for (size_t u = 0u; u < transport_boxes_count; ++u)
        {
            cout << transport_boxes[u] << (u == transport_boxes_count - 1 ? "" : " + ");
        }
        cout << endl;
    }
 
    return 0;
}
1
99 / 98 / 11
Регистрация: 12.09.2016
Сообщений: 195
20.05.2019, 20:37  [ТС]
SomniPhobia, а можешь, пожалуйста, сам принцип алгоритма рассказать?
0
 Аватар для SomniPhobia
602 / 439 / 137
Регистрация: 22.11.2017
Сообщений: 1,405
21.05.2019, 10:05
Лучший ответ Сообщение было отмечено Gaveyn как решение

Решение

Gaveyn, привет!
Могу.
Принцип работы с рычажными весами.
На одной чаше лежит груз, массу которого необходимо узнать. Вторая чаша для гирек пока пуста. Правило постановки гирь на чашу такого: Сперва ставим самую тяжёлую гирю что есть. Если она перевешивает груз, то снимаем её с чаши и ставим следующую по убыванию массы гирю. Тоже перевешивает - снимаем с чаши и ставим полегче и т. д. Как только гиря перестала перевешивать груз (чаша весов с грузом опустилась хоть и поставили гирю), берём следующую по убыванию массы гирю и кладём её рядом к первой. И так подбираем по убыванию вторую гирю пока груз не перевесит две гири. Всё сводится к тому, чтобы дойти до самых лёгких гирек что есть (или до требуемой точности измерения), пытаясь выровнять положение чаш весов друг напротив друга.
Алгоритм в коде. За основу взят принцип работы с рычажными весами, но он был модернизирован.
Собираем все массы грузов в контейнер boxes. Сортируем его по убыванию массы грузов (левый самый тяжёлый, правый самый лёгкий).
Затем проходим по этому контейнеру, содержащему массы грузов по убыванию.
Первый груз (самый тяжёлый) грузим на первое транспортное средство (далее по тексту как ТС), следующий груз в контейнере boxes чуть полегче грузим на второе ТС, чуть полегче на 3 ТС и т. д. Сколько у нас ТС задано (значение переменной q), столько ТС и нагружается.
Принцип таков.
Контейнер transport_total_mass изначально содержит нули в количестве q. То есть изначально каждое ТС везёт 0 единиц массы. Нагружаем так: ищем ТС, у которого минимальная масса груза. В него грузим очередной груз как можно большей массы. Загрузили. Снова ищем минимум. Туда загружаем груз полегче. Снова ищем минимум по контейнеру transport_total_mass. То есть то ТС, которое загружено меньше остальных. Туда груз загружаем полегче.
Пример
Всего ТС 3
Есть грузы массой 1 2 3 4 5 10 8
Сортировка
10 8 5 4 3 2 1
До распределения содержание контейнера transport_total_mass
0 0 0
Распределение
Проход 0 (в руках груз массой 10)
10 0 0
Проход 1 (в руках груз массой 8)
10 8 0
Проход 2 (в руках груз массой 5)
10 8 5
Проход 3 (в руках груз массой 4)
10 8 9
Проход 4 (в руках груз массой 3)
10 11 9
Проход 5 (в руках груз массой 2)
10 11 11
Проход 6 (в руках груз массой 1)
11 11 11
Итог распределения
11 11 11
Принцип понятен?
1
99 / 98 / 11
Регистрация: 12.09.2016
Сообщений: 195
21.05.2019, 22:59  [ТС]
SomniPhobia, Спасибо большое, очень помогли разобраться!

Добавлено через 2 часа 43 минуты
SomniPhobia, Извините, а вы уверены что этот алгоритм работает всегда? Я ввел Q = 2, а далее
N = { 8 13 16 18 14 12}
По-идее должно быть Q1 = { 8+18+14 } , а Q2 = { 13+16+12}, тогда получилось бы что первый повезет груз массой 40, а второй повезет груз массой 41. (разница в 1)
Ваша же программа предлагает распределить так: Q1= { 18+13+8}, Q2 = {16+14+12}. Тогда один повезет груз массой 39, а другой массой 42 (разница 3)
1
 Аватар для SomniPhobia
602 / 439 / 137
Регистрация: 22.11.2017
Сообщений: 1,405
22.05.2019, 11:50
Gaveyn, пожалуйста!
Цитата Сообщение от Gaveyn Посмотреть сообщение
Я ввел Q = 2, а далее
N = { 8 13 16 18 14 12}
Алгоритм работает верно, просто даёт не тот результат, что должен быть в этой ситуации. Значит этот алгоритм к этой задаче не применим или применим частично.
Что ещё можно придумать? Самый последний способ - полный перебор всех сочетаний (очень долго).
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
22.05.2019, 11:50
Помогаю со студенческими работами здесь

Один метод должен в новой ведомости размещать студентов в алфавитном порядке. Другой – сохранять только студентов с долей оценок (равных заданной оц
Один метод должен в новой ведомости размещать студентов в алфавитном порядке. Другой – сохранять только студентов с долей оценок...

Разделить вложенный список на примерно равные части
Здравствуйте, как мне разделить вложенный список на примерно равные части? Допустим есть list = ,,,,,,] Таких вложенных документов...

Разделить таблицу на заданное количество равных частей
Добрый вечер! Прошу подсказать как решить мою задачу. Есть таблица, которая состоит из 3х столбцов (лист Было). Нужно разделить...

Разделить файл txt на несколько равных маленьких файлов
Пожалуйста помогите. Есть большой txt там 1335478 символов Как сделать чтоб он создал папку а в ней 667 файлов по 2000 символов в каждом...

Разделить блок, например <div> на три равных станицы
Господа, подскажите пожалуйста, делаю хедер и необходимо его разделить на три жестко закрепленных по ширине части. Как это лучше сделать,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Новые блоги и статьи
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
Фото: Daniel Greenwood
kumehtar 13.11.2025
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru