Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
0 / 0 / 0
Регистрация: 08.05.2016
Сообщений: 73

Приближенный алгоритм. Грузовики и камни

16.05.2017, 15:36. Показов 1359. Ответов 1
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Подскажите алгоритм, ибо мой не проходит по времени(ограничения 1 секунда).
Я делал так: сортировал грузовики и камни и последовательно шел по массиву грузовиков и пробовал запихивать камень, если он не пихался, то шел по массиву камней так до конца.
Второй метод: отсортил камни и грузовики и в этот раз, если камень не пихется, то ищем в массиве камней наиболее подходящий камень за logN( постоянно разделяя массив камней на 2 подмассива и брал тот, в котором должен быть камень, который поместиться в машину) Все 2 алгоритма не проходят по времени. Подскажите, может кто уже решал такие задачи?
Имеется n камней и m машин в очереди. Камни характеризуются массой, машины — грузоподъемностью. Необходимо определить порядок загрузки, при котором минимизируется число используемых машин.

Замечание

Известно, что любой камень помещается в любую машину, а также, что если искомое размещение существует, то общее число машин не менее чем вдвое превосходит минимально возможное число машин.

Формат входного файла

В первой строке находится число m грузовиков (1 ≤ m ≤ 300 000). В следующих m строках записаны грузоподъёмности грузовиков. В следующей строке находится число n камней (1 ≤ n ≤ 300 000). Далее в n строках записаны массы камней.

Формат выходного файла


Если решение существует, то выведите 2m + 1 строк. В первой — число m, а далее для каждой машины в первой строке должна находиться грузоподъёмность грузовика, а во второй — последовательно через пробел массы камней, положенных в грузовик (пустая строка, если в грузовик ничего не положено). Число используемых машин не должно превышать минимально возможное более чем в два раза.
Если решений нет, то выведите no solution.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
16.05.2017, 15:36
Ответы с готовыми решениями:

Что такое приближенный алгоритм и в чем отличие от эвристического или жадного?
Правильно ли я понимаю, что приближенный алгоритм - это алгоритм, который всегда дает почти точное решение и его точность доказана, в то...

Фильм-обзор об играх про грузовики
Увидел на ютубе качественный фильм-обзор на игры о грузовиках, если есть любители оных Советую глянуть OdUpsxk7yog brN2qc7RFCY ...

Класс: Создать абстрактный класс Mashine и подклассы: автомобили, грузовики.
Создать абстрактный класс Mashine, затем подклассы: автомобили, грузовики. Создать интерфейсы: грузовые и легковые. Организовать...

1
0 / 0 / 0
Регистрация: 08.05.2016
Сообщений: 73
21.05.2017, 19:44  [ТС]
Так долго не отвечали, что пришлось самому решить(
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstddef>
#include <cmath>
#include <stack>
#include <vector>
#include<set>
#include <ctime>
#include <algorithm>
 
using namespace std;
    int size1;
    int size2;
 
int main()
{
    FILE *filei = fopen("input.txt", "r");
    FILE *fileo = fopen("output.txt", "w");
 
    fscanf(filei,"%d", &size1);
    vector <int> a(size1);
    vector <int> aOr(size1);
    int wD;
    for (int i = 0; i < size1; ++i) {
        fscanf(filei, "%d", &wD);
        a[i] = wD;
        aOr[i] = wD;
    }
    sort(a.rbegin(), a.rend());
    sort(aOr.rbegin(), aOr.rend());
    
 
    fscanf(filei, "%d", &size2);
    vector <int> b(size2);
    int min = 10000000000000;
    for (int i = 0; i < size2; ++i) {
        fscanf(filei, "%d", &wD);
        b[i] = wD;
        if (wD < min) min = wD;
    }
 
    vector<vector<int>> out = *new vector<vector<int>>(size2);
     
    int idx = 0;
    int board = 0;
    int boardHead = 0;
 
    while (idx != size2) {
        bool is = true;
        for (int g = boardHead; g < board; ++g) {
           if (a[g] >= b[idx]) {
               a[g] -= b[idx];
               out[g].push_back(b[idx]);
               ++idx;
               if (a[g] < min) {
                   iter_swap(a.begin(), a.begin() + g);
                   iter_swap(aOr.begin(), aOr.begin() + g);
                   iter_swap(out.begin(), out.begin() + g);
                   ++boardHead; 
               }
               is = false;
               break;
           }
        }
        if (is) {
 
            if (board == size1) {
                fprintf(fileo, "no solution");
                return 0;
            }
            ++board;
        }
    }
 
    fprintf(fileo,"%d", size1 );
    fprintf(fileo, "\n");
    for (int i = 0; i < size1; ++i) {
        fprintf(fileo,"%d", aOr[i]);
        fprintf(fileo, "\n");
        for (int h = 0; h < out[i].size(); ++h) {
            fprintf(fileo,"%d", out[i][h]);
            fprintf(fileo, " ");
        }
        fprintf(fileo, "\n");
    }
    return 0;
}
Алгоритм:
First-fit algorithm
This is a very straightforward greedy approximation algorithm. The algorithm processes the items in arbitrary order. For each item, it attempts to place the item in the first bin that can accommodate the item. If no bin is found, it opens a new bin and puts the item within the new bin.
It is rather simple to show this algorithm achieves an approximation factor of 2, that is, the number of bins used by this algorithm is no more than twice the optimal number of bins. In other words, it is impossible for 2 bins to be at most half full because such a possibility implies that at some point, exactly one bin was at most half full and a new one was opened to accommodate an item of size at most V/2. But since the first one has at least a space of V / 2, the algorithm will not open a new bin for any item whose size is at most V / 2. Only after the bin fills with more than V / 2 or if an item with a size larger than V / 2 arrives, the algorithm may open a new bin.
Thus if we have B bins, at least B − 1 bins are more than half full. Therefore, {\displaystyle \sum _{i=1}^{n}a_{i}>{\tfrac {B-1}{2}}V} \sum_{i=1}^n a_i>\tfrac{B-1}{2}V. Because {\displaystyle {\tfrac {\sum _{i=1}^{n}a_{i}}{V}}} \tfrac{\sum_{i=1}^n a_i}{V} is a lower bound of the optimum value OPT, we get that B − 1 < 2OPT and therefore B ≤ 2OPT.[6] See the analysis below for better approximation results.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
21.05.2017, 19:44
Помогаю со студенческими работами здесь

Приближенный бинарный поиск
Реализуйте алгоритм приближенного бинарного поиска. Входные данные В первой строке входных данных содержатся числа N и K. Во второй...

Приближенный двоичный поиск
Доброго времени суток, форумчане. Задача такая: В первой строке входных данных содержатся числа N и K (0 &gt; N,K &gt;100001 ). Во...

Приближенный бинарный поиск
В FoxPro есть команда SET NEAR ON, по которой указатель ставится на ближайшее к заказанному числу значение. Допустим, есть ряд (1, 3, 4, 7,...

Приближенный двоичный поиск
Помогите пожалуйста решить задачую Заранее спасибо! Реализуйте алгоритм приближенного бинарного поиска. Входные данные В первой...

ADOTable.Locate, приближенный поиск
Здравствуйте, помогите пожалуйста сделать приближенный поиск. Это значит если нет...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Новые блоги и статьи
моя боль
iceja 24.01.2026
Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
Модель сукцессии микоризы
anaschu 24.01.2026
Решили писать научную статью с неким РОманом
http://iceja.net/ математические сервисы
iceja 20.01.2026
Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов
iceja 18.01.2026
Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока
igorrr37 16.01.2026
/ * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .
Восстановить юзерскрипты Greasemonkey из бэкапа браузера
damix 15.01.2026
Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru