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

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

20.05.2019, 15:38. Показов 1910. Ответов 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,407
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,407
20.05.2019, 17:31
Вот ещё скрины работы программы.
Миниатюры
Разделить N контейнеров на Q примерно равных долей   Разделить N контейнеров на Q примерно равных долей   Разделить N контейнеров на Q примерно равных долей  

1
 Аватар для SomniPhobia
602 / 439 / 137
Регистрация: 22.11.2017
Сообщений: 1,407
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,407
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,407
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,407
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
Ответ Создать тему
Новые блоги и статьи
AkelPad-скрипты, структуры, и немного лирики..
testuser2 05.04.2026
Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
Отображение реквизитов в документе по условию и контроль их заполнения
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II
kumehtar 04.04.2026
Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
Вывод диалогового окна перед закрытием, если документ не проведён
Maks 04.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .
Программный контроль заполнения реквизитов табличной части документа
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .
wmic не является внутренней или внешней командой
Maks 02.04.2026
Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/
Программная установка даты и запрет ее изменения
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .
Вывод данных в справочнике через динамический список
Maks 01.04.2026
Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru