Форум на Исходниках.RU

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

esperanto — Mon, 25 May 2020 20:25:10 +0000

esperanto:

Цитата prografix @ 19.02.20, 10:01

В задачу не вникал, но похоже, что можно применить динамическое программирование.

не знаешь хороший курс с юбтуба по динамическому программированию?

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

Black_Dragon — Mon, 25 May 2020 11:56:19 +0000

Black_Dragon: У меня вопросы про постановку задачи. Чиста из любопытства о приземленности задачи (или для усложнения ее).

1) К станку идут несколько очередей заданий, длина очереди - единица?
2) Есть общая очередь (главная/центральная) со всеми заданиями? Или каждая очередь станка только со своими заданиями (тогда длина очереди может >1)
3) Первое задание из общей очереди идет в первую очередь станка и т.д. распределяется по другим очередям станка?
4) Выполненное задание освобождает место и из общей очереди туда перемещается первое задание?
5) Станок ждет, когда поступит задание в освободившееся место или начинает обрабатывать из оставшихся? Ну т.е. станок так сделан: выполнил задание, и начинает выбирать из существующих (пока на свободное место загружается новая задача по rs-232) :D
6) А в общей очереди их перераспределять можно, т.е. ее за ране подготовить?
7) А станок вообще знает, какие задачи в главной очереди или только те, которые ожидают исполнение?

Т.е. получается так, станок принадлежит Васи, а задачи от разных клиентов разного ранга.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

AVA12 — Sun, 03 May 2020 19:33:33 +0000

AVA12:

Цитата

Поразрядная сортировка, кстати, на самом деле тоже не O(N), а O(N log M), где M - разрядность данных.

Разрядность данных - это не длина строкового ключа, которая может быть любой (кстати, почему log M, а не M?). Разрядность для массива чисел - это константа, так что нет смысла ее учитывать.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

swf — Sun, 03 May 2020 19:11:58 +0000

swf: Спасибо, буду разбираться :)

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

amk — Sun, 03 May 2020 18:45:27 +0000

amk: Моё сообщение от 2 марта посвящено анализу условий, при которых план работы оптимален локально (под спойлером). А ниже спойлера пояснение, почему он оптимален и глобально.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

swf — Sun, 03 May 2020 17:49:11 +0000

swf:

Цитата amk @ 03.05.20, 15:51

swf, как уже выяснилось, эта задача сводится к сортировке и имеет сложность O(N log N)

А я что-то не поняла. Как доказали, что сортировка даёт оптимальное решение?

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

amk — Sun, 03 May 2020 17:45:47 +0000

amk:

Цитата AVA12 @ 03.05.20, 15:54

Отсортировать можно и за O(N)!

Только в частных случаях, когда на исходные данные накладываются некоторые ограничения.

Поразрядная сортировка, кстати, на самом деле тоже не O(N), а O(N log M), где M - разрядность данных.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

AVA12 — Sun, 03 May 2020 15:54:59 +0000

AVA12:

Цитата

задача сводится к сортировке и имеет сложность O(N log N)

Почему именно O(N log N)? Отсортировать можно и за O(N)!

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

amk — Sun, 03 May 2020 15:51:18 +0000

amk: swf, как уже выяснилось, эта задача сводится к сортировке и имеет сложность O(N log N)

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

swf — Sun, 26 Apr 2020 22:04:50 +0000

swf: В списке модельных NP-полных задач из старого Гэри, Джонсона такой нет.
Задача, скорее всего, полиномиально сводится к коммивояжеру. Но это, конечно, нужно доказать.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

JoeUser — Wed, 04 Mar 2020 08:04:14 +0000

JoeUser: amk, да, я проверил - у меня вариант хуже. Из 1000 рандомных наборов, у меня около 30 неоптимальные (ошибочные).

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

amk — Tue, 03 Mar 2020 16:07:53 +0000

amk: Держи

Цитата AVA12 @ 19.02.20, 11:16

Кажется, я что-то нащупал.
С одной стороны, нужно выполнять задания в порядке убывания возрастания времени выполнения, чтобы простой был минимальным. С другой стороны, нужно выполнять задания в порядке убывания штрафа, чтобы меньше денег натикало. Объединяем оба требования, для каждой задачи вычисляем отношение штраф/время и сортируем их в порядке убывания этого отношения. Получается, вроде бы, неплохо.

Ну и конкретно, на что обратить внимание

Цитата AVA12 @ 19.02.20, 11:16

вычисляем отношение штраф/время

Цитата AVA12 @ 19.02.20, 11:16

сортируем их в порядке убывания этого отношения

Я предложил то же самое отношение, только делил время на штраф, и соответственно, сортировал по возрастанию. У меня в спойлере это отношение даже выводится. Специально потратил десяток минут.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

JoeUser — Mon, 02 Mar 2020 19:16:49 +0000

JoeUser:

Цитата amk @ 02.03.20, 17:41

А правильный ответ почти сразу дал AVA12

Прошу его еще раз процитировать/уточнить, чтобы провести замеры.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

amk — Mon, 02 Mar 2020 17:41:26 +0000

amk: Легко можно показать, что решение локально оптимально, если величина Duration/Cost не убывает.

Скрытый текст

Рассмотрим последовательность работ и выделим в ней две соседние работы
W[1] ... W[k+1] W[k+2] .... W[N]
         D[k+1] D[k+2]
         C[k+1] C[k+2]
Как легко заметить штраф за работы выполняемые до них не меняется, если их поменять местами. Так же не меняется штраф за последующие работы.

Запишем общий штраф для рассмотренной последовательности и последовательности, в которой эти работы поменяны местами.
Ss + Ds*C[k+1] + (Ds + D[k+1])*C[k+2] + Se
Ss + Ds*C[k+2] + (Ds + D[k+2])*C[k+1] + Se

Раскроем скобки и объединим совпадающие в обоих выражениях слагаемые
Ss + Ds*(C[k+1] + C[k+2]) + Se + D[k+1]*C[k+2] = S + D[k+1]*C[k+2]
Ss + Ds*(C[k+1] + C[k+2]) + Se + D[k+2]*C[k+1] = S + D[k+2]*C[k+1]

Должно выполняться
S + D[k+1]*C[k+2] <= S + D[k+2]*C[k+1]

D[k+1]*C[k+2] <= D[k+2]*C[k+1]

D[k+1]/C[k+1] <= D[k+2]/C[k+2]

Добавлено 02.03.20, 17:43
Вообще говоря, поскольку данное соотношение не зависит от места задачи в очереди выполнения локально оптимальное решение должно быть оптимальным и глобально. А потому непонятно, почему у JoeUser'а иногда получаются не самые оптимальные решения. Или он по какому-то другому критерию сортирует?

Добавлено 02.03.20, 17:47
Разобрался. Он действительно в качеств отношения использует другое значение и получает неточный результат.

А правильный ответ почти сразу дал AVA12.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

JoeUser — Mon, 02 Mar 2020 16:59:52 +0000

JoeUser: Что-то ТС молчит как рыба об лед! :lol: У меня еще появились идеи ... только мне одному они ни разу не упали.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

JoeUser — Sun, 01 Mar 2020 15:05:37 +0000

JoeUser:

Цитата AVA12 @ 01.03.20, 14:49

Не совсем понятно, для чего тут нужны суммы.

Я уже объяснял вой взгляд ранее - посчитал, что каждый параметр вносит свой вклад в расчеты. А как его (вклад) можно определить? Самое простое - разделить его на сумму остальных и оценить долю. Повторюсь - такой метод расчетов просто получился путем догадок! Никаких точных математических обоснований, никаких прочих формул и правил.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

AVA12 — Sun, 01 Mar 2020 14:49:11 +0000

AVA12: Короче говоря, итоговый коэффициент k[i] = (P[i] / T[i]) * (sum(T) - T[i]) / (sum(P) - P[i]), где P - это штрафы, а T - время выполнения. Не совсем понятно, для чего тут нужны суммы. Все, что они делают - это добавляют нелинейности к итоговым коэффициентам, а поскольку нас интересуют только отношения больше/меньше, эта нелинейность ничего не меняет.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

JoeUser — Sun, 01 Mar 2020 14:02:33 +0000

JoeUser:

Цитата AVA12 @ 01.03.20, 12:47

Но хотелось бы увидеть описание алгоритма (или формулы).

Хорошо, попробую на пальцах ... :-?

Пусть дан список работ. Каждая работа представлена в списке тройкой [порядковый_номер_работы, продолжительность_работы, штраф_за _простой]

{{0, 1, 1}, {1, 2, 3}, {2, 3, 2}};

Нам нужно для каждой работы вычислить "взвешенный коэффициент"

Работа 0

sum_r = равна сумме всех штрафов, кроме работы №0 (равна 5);
sum_j = равна сумме всех продолжительностей работ, кроме работы №0 (равна 5);
k1 = промежуточный коэффициент, равный (штраф_работы_№0/sum_r) = 0.2
k2 = промежуточный коэффициент, равный (продолжительность_работы_№0/sum_j) = 0.2
взвешенный коэффициент работы №0 = k1/k2 (равен 1.0)

Работа 1

sum_r = равна сумме всех штрафов, кроме работы №1 (равна 3);
sum_j = равна сумме всех продолжительностей работ, кроме работы №1 (равна 4);
k1 = промежуточный коэффициент, равный (штраф_работы_№1/sum_r) = 1
k2 = промежуточный коэффициент, равный (продолжительность_работы_№1/sum_j) = 0.5
взвешенный коэффициент работы №1 = k1/k2 (равен 2.0)

Работа 2

sum_r = равна сумме всех штрафов, кроме работы №2 (равна 4);
sum_j = равна сумме всех продолжительностей работ, кроме работы №2 (равна 3);
k1 = промежуточный коэффициент, равный (штраф_работы_№2/sum_r) = 0.5
k2 = промежуточный коэффициент, равный (продолжительность_работы_№2/sum_j) = 1
взвешенный коэффициент работы №2 = k1/k2 (равен 0.5)

Значит, работы нужно расположить по убыванию их "взвешенных коэффициентов" в порядке:

1-0-2, вот так: {{1, 2, 3}, {0, 1, 1}, {2, 3, 2}}

Считаем суммарный штраф: 2*(1+2) +1*(2) = 8

Проверяем перебором все перестановки:

{1,2,3}, {0,1,1}, {2,3,2} = 8
{0,1,1}, {1,2,3}, {2,3,2} = 9
{1,2,3}, {2,3,2}, {0,1,1} = 9
{0,1,1}, {2,3,2}, {1,2,3} = 14
{2,3,2}, {1,2,3}, {0,1,1} = 14
{2,3,2}, {0,1,1}, {1,2,3} = 15

Проверка прошла удачно!
Найденное значение по взвешенным коэффициентам равно минимальному значению при полном переборе.
Бинго.

Добавлено 01.03.20, 14:07

Цитата AVA12 @ 01.03.20, 12:47

возможно даже, удастся его скомпилировать и запустить)

Да, пожалуйста, https://ideone.com/y0IcNc, только без последнего длинного теста, ибо онлан-компилятор обрубает по времени исполнения.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

AVA12 — Sun, 01 Mar 2020 12:47:41 +0000

AVA12: JoeUser, это раздел "Алгоритмы", а не "C++". То, что есть исходник программы - это, конечно, хорошо (возможно даже, удастся его скомпилировать и запустить). Но хотелось бы увидеть описание алгоритма (или формулы).

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

JoeUser — Sat, 29 Feb 2020 23:54:00 +0000

JoeUser: ADD> В предыдущем моем посте в прикрепленном архиве - текстовые файлы. Которые получаются путем перехвата вывода из STDOUT (типа ./myprog > 1). А смотреть и сравнивать нужно вот это:

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

JoeUser — Sat, 29 Feb 2020 23:46:18 +0000

JoeUser: Вроде бы нашел интересное решение :)

Назову его путем "сортировки взвешенных коэффициентов". Предпосылка простая - каждая работа вносит определенный вклад в общий штраф, когда выполняется, и вносит вклад в общее время выполнения. Если как-то соотнести эти "вклады" - можно "взвесить" эти коэффициенты. Соответственно, работы с большими коэффициентами влияния желательно расположить раньше работ с меньшими. Такова была моя гипотеза. И я решил провести ее проверку. Для этого написал несложную программу. Суть которой - создание тестов на случайных данных и их оценка моей методикой и полным перебором. Ну и сравнение, какой суммарный штраф получается путем сортировки взвешенных коэффициентов, и что нам дает точный полный перебор.

Вот программа:

Скрытый текст

#include <algorithm>

#include <iostream>

#include <iterator>

#include <locale>

#include <string>

#include <vector>

#include <ctime>

#include <map>

using namespace std;

struct JobsElement {

unsigned int Num;

unsigned int Duration;

unsigned int Penalty;

JobsElement(unsigned int iNum, unsigned int iDuration, unsigned int iPenalty):

Num(iNum), Duration(iDuration), Penalty(iPenalty) {}

bool operator<(const JobsElement& rhs) const {

return (Num < rhs.Num);

}

};

typedef vector<JobsElement> JobsType;

typedef map<unsigned int, double> RatioType;

// Распечатка вектора

void PrintVector(JobsType& iJobs, string iStr, string iEnd) {

if (iStr.length())

cout << iStr << endl;

for (size_t i = 0; i < iJobs.size(); i++) {

cout << iJobs[i].Num << ": {" << iJobs[i].Duration << "," << iJobs[i].Penalty << "}";

cout << ((i < iJobs.size() - 1) ? ", " : "");

}

if (iEnd.length())

cout << " " << iEnd;

cout << endl;

}

// Вычисление суммарного штрафа для последовательности работ

auto Penalty(JobsType& iJobs) {

int Ret = 0;

for (size_t i = 0; i < iJobs.size(); i++)

for (size_t j = i + 1; j < iJobs.size(); j++)

Ret += iJobs[i].Duration * iJobs[j].Penalty;

return Ret;

}

// Вычисление "взвешенных" штрафных коэфициентов

auto CountingRatio(JobsType& iJobs) {

RatioType Ratio;

for (unsigned int i = 0; i < iJobs.size(); i++) {

int sum_r = 0;

int sum_j = 0;

for (unsigned int j = 0; j < iJobs.size(); j++) {

if (i != j) {

sum_j += iJobs[j].Duration;

sum_r += iJobs[j].Penalty;

}

double k1 = (iJobs[i].Penalty) / (double) sum_r;

double k2 = (iJobs[i].Duration) / (double) sum_j;

Ratio[i] = k1 / (double)k2;

}

JobsType Ret;

std::copy(iJobs.begin(), iJobs.end(), std::back_inserter(Ret));

std::sort(Ret.begin(), Ret.end(), [&](const JobsElement & iA, const JobsElement & iB)->auto {

return !(Ratio[iA.Num] < Ratio[iB.Num]);

});

return Ret;

}

// Перебор и оценка вариантов

auto CountingBruteforce(JobsType& iJobs) {

vector<pair<unsigned int, JobsType>> Tmp;

do {

int Pen = Penalty(iJobs);

Tmp.push_back({Pen, iJobs});

} while (std::next_permutation(iJobs.begin(), iJobs.end()));

sort(Tmp.begin(), Tmp.end(), [&](const pair<unsigned int, JobsType>& iA, const pair<unsigned int, JobsType>& iB)->auto {

return iA.first < iB.first;

});

for (auto&& i : Tmp)

PrintVector(i.second, "", to_string(i.first));

}

// Подготовка нового вектора

void PrepareVector(JobsType& iJobs, const size_t iLen) {

iJobs.clear();

for (unsigned int i = 0; i < iLen; i++)

iJobs.push_back(JobsElement(i, 1 + std::rand() % 9, 1 + std::rand() % 9));

}

// запуск теста

void RunTest(JobsType& iJobs, const size_t iNum) {

PrintVector(iJobs, "Test #" + to_string(iNum) + ":\n------------------------------------------------------", "");

auto Res = CountingRatio(iJobs);

PrintVector(Res, "Result vector:", "");

cout << "Result penalty: " << Penalty(Res) << endl;

CountingBruteforce(iJobs);

cout << endl;

}

int main() {

std::srand(unsigned(std::time(0)));

// Тест 1: ручное задание параметров и числа работ

JobsType Jobs = {{0, 1, 1}, {1, 2, 3}, {2, 3, 2}};

RunTest(Jobs, 1);

// Тест 2

PrepareVector(Jobs, 4);

RunTest(Jobs, 2);

// Тест 3

PrepareVector(Jobs, 5);

RunTest(Jobs, 3);

// Тест 4

PrepareVector(Jobs, 6);

RunTest(Jobs, 4);

// Тест 5

PrepareVector(Jobs, 7);

RunTest(Jobs, 5);

return 0;

}

К сообщению прикрепил вывод программы из трех последовательных запусков. Результаты прекрасные, ящетаю! :lol:

Но есть и ложка "дегтя" ... сами понимаете - алгоритм получен эмпирическим путем, поэтому может быть неточен. И это тоже я проверил. В одном из тестов полный перебор дал минимальный штраф 47 единиц (при мах=540), а мой алгоритм на коэффициентах дал 48. Но это было примерно в одном 1 из 20 запусков. Запускал и проверял руками вывод. Может повезло.

И тем не менее! Если "взвешенные коэффициенты" на любых вменяемых диапазонах значений дают такой результат, то на количестве работ 1000 моей методике пока равных нет, пока не найдена лучшая. Для сравнения: полный перебор дает N! вариантов расчета суммарного штрафа, а мой алгоритм N*(N-1) расчета коэффициентов + 1 расчет суммарного штрафа. Что такое 1000! дело понятное.

В общем, смотрите, экспериментируйте, критикуйте. Возможно где-то чё-то не так.

:thanks:

res.7z (, : 776)

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

FasterHarder — Thu, 20 Feb 2020 11:15:58 +0000

FasterHarder:

Цитата amk @ 20.02.20, 11:00

(а может быть, полученная последовательность и не обязательно оптимальна).

а добиться оптимальности можно лишь полным перебором

Цитата Akina @ 19.02.20, 13:29

Однозначно она.

самое страшное, что решил еще одну задачку, которая имеет ТАКУЮ ЖЕ СЛОЖНОСТЬ, как эту, примерно за 4-7 мин. (построив мат.модель) и там все прекрасно :lol:
здесь что-то непонятное происходит..ну не знаю, конечно, всякое бывает...

в др.алгоритме (здесь его никто не приводил) работают ЧЕРЕЗ произведения, отбирая нужное задание из оставшихся....

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

amk — Thu, 20 Feb 2020 11:00:06 +0000

amk:

Цитата FasterHarder @ 20.02.20, 10:25

мне казалось, что {a, b, c} --> {abc, acb, bac, aca, cab, cba}, в его алгоритме вообще переборов вроде НЕТ

Потому что он дал тебе приближённый алгоритм с эмпирическим правилом сортировки. Да, на большинстве данных он даёт оптимальный или близкий к оптимальному результат, но оптимальность его в общем случае не очевидна (а может быть, полученная последовательность и не обязательно оптимальна).

Хотя, сдаётся мне, можно доказать локальную оптимальность такой сортировки относительно обменов подпоследовательностей (типа abc...de...fgh<->abe...fc...dgh). А в таком случае может оказаться, что это простое правило даёт оптимальное решение.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

FasterHarder — Thu, 20 Feb 2020 10:25:07 +0000

FasterHarder:

Цитата Akina @ 19.02.20, 19:03

Да есть у него всё.

ок, значит я не до конца понимаю, что такое переборы всех возможных вариантов
мне казалось, что {a, b, c} --> {abc, acb, bac, aca, cab, cba}, в его алгоритме вообще переборов вроде НЕТ :D , ну не знаю...

Цитата Akina @ 19.02.20, 19:03

Затем, что полный перебор - штука долгая. И не исключено, что ты можешь прервать процесс в середине, если текущее решение тебя в принципе устраивает.

это я тоже не понимаю
если для получения ТОЧНОГО ДЕТЕРМИНИРОВАННОГО результата требуется перебрать ВСЕ ВОЗМОЖНЫЕ варианты, то как я могу что-то прервать в середине обработки..
+ я вообще не выкупаю, какая связь между ПЕРЕБОРОМ ВСЕХ ВАРИАНТОВ и сортировкой...когда перебираем все, то сортировка ведь совсем не нужна, ну не знаю...не знаю...всякое, конечное, бывает...не знаю...

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

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

Akina — Wed, 19 Feb 2020 19:03:43 +0000

Akina:

Цитата FasterHarder @ 19.02.20, 13:42

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

Да есть у него всё.

Цитата FasterHarder @ 19.02.20, 13:42

а зачем что-то сортировать, если и так будут всевозможные переборы вариантов?

Затем, что полный перебор - штука долгая. И не исключено, что ты можешь прервать процесс в середине, если текущее решение тебя в принципе устраивает. А при сортировке вероятность "хороших решений" выскочить раньше - выше.
Нет, если нужен абсолютный минимум, то и вправду пофиг на сортировку.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

FasterHarder — Wed, 19 Feb 2020 13:42:12 +0000

FasterHarder: Akina, т е способ предложенный AVA12, не совсем точен? :no-sad:
ведь в его варианте нет никакого перебора или я что-то не понимаю относительно этих переборов...

Добавлено 19.02.20, 13:45

Цитата Akina @ 19.02.20, 13:29

Причём перебор с удачной сортировкой на равномерных

а зачем что-то сортировать, если и так будут всевозможные переборы вариантов? :huh:

совсем я запутался...

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

Akina — Wed, 19 Feb 2020 13:29:35 +0000

Akina:

Цитата FasterHarder @ 19.02.20, 08:23

Или это NP-полная задача, т е нужен ПОЛНЫЙ перебор ВСЕХ возможных вариантов??

Однозначно она. Причём перебор с удачной сортировкой на равномерных данных должен дать наибольшее количество отбрасываемых вариантов и. соответственно, более быструю сходимость.
Что до "удачной сортировки"... Задания с максимальным удельным штрафом и с минимальным временем выполнения желательно ставить в начало перебора, так что я бы ратовал за, в первом приближении, сортировку по (штраф/время) по убыванию, наверное.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

AVA12 — Wed, 19 Feb 2020 12:18:33 +0000

AVA12:

Цитата

Станку В ЛЮБОМ случае для выполнения всех заданий потребуется времени T(1) + T(2) + ... + T(N). Какая ему разницы, какое задание выполнять в данный момент времени (на штраф внимания не обращаем сейчас)

Станку без разницы, а вот для задач с тикающими счетчиками разница есть. Если твой первый пример выполнять в порядке возрастания T, то общий простой задач будет 1 + (1 + 4) = 6 часов. А если в порядке убывания T, то простой будет уже 10 + (10 + 4) = 24 часа.

Цитата

допустим характеристики {T; C} заданий №7 и №28 такие соот-но {4: 8}, {6; 12}, т е у них РАВНЫЕ отношения = 2/1, то их можно выполнять В ЛЮБОМ порядке?

Ну, в одном случае штраф будет 4 * 12, а в другом 6 * 8, так что смотри сам.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

FasterHarder — Wed, 19 Feb 2020 11:48:41 +0000

FasterHarder: AVA12, да, круто у тебя, конечно, получилось! ;) а главное, что так просто: отношение + отсортированный массив.

но вот кое-что еще.

Цитата AVA12 @ 19.02.20, 11:16

нужно выполнять задания в порядке убывания штрафа, чтобы меньше денег натикало

вот это я понимаю хорошо, т е нужно как можно быстрее исполнить задания с высоким штрафом

Цитата AVA12 @ 19.02.20, 11:16

нужно выполнять задания в порядке убывания времени выполнения

вот тут что-то я на 100% не ухватываю. Станку В ЛЮБОМ случае для выполнения всех заданий потребуется времени T(1) + T(2) + ... + T(N). Какая ему разницы, какое задание выполнять в данный момент времени (на штраф внимания не обращаем сейчас)

Цитата AVA12 @ 19.02.20, 11:16

штраф/время и сортируем их в порядке убывания этого отношения

вот честно, я вообще не понимаю, почему взял отношение C/T, а не T/C (время/штраф), например.

Кстати, данные читаются из файла, поэтому можно сразу, считав пару данных {T, C} вставлять их отношение в одномерный массив, сохранив упорядоченность на убывание.
кстати, как я понимаю, N уже может быть хоть лям - не критично.

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

P.S. был уверен на 90%, что тут графы замешаны, оказалось - все проще, хотя, это все очень непросто все равно)

Добавлено 19.02.20, 11:56
и еще такой момент: допустим характеристики {T; C} заданий №7 и №28 такие соот-но {4: 8}, {6; 12}, т е у них РАВНЫЕ отношения = 2/1, то их можно выполнять В ЛЮБОМ порядке?

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

AVA12 — Wed, 19 Feb 2020 11:16:31 +0000

AVA12: Кажется, я что-то нащупал.
С одной стороны, нужно выполнять задания в порядке ~~убывания~~ возрастания времени выполнения, чтобы простой был минимальным. С другой стороны, нужно выполнять задания в порядке убывания штрафа, чтобы меньше денег натикало. Объединяем оба требования, для каждой задачи вычисляем отношение штраф/время и сортируем их в порядке убывания этого отношения. Получается, вроде бы, неплохо.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

FasterHarder — Wed, 19 Feb 2020 10:35:24 +0000

FasterHarder:

Цитата prografix @ 19.02.20, 10:01

В задачу не вникал, но похоже, что можно применить динамическое программирование.

думал об этом, но это не отменяет того, что нужен алгоритм)
а лучше вникни, т к там все достаточно просто + великолепная поясняющая картинка есть

Цитата AVA12 @ 19.02.20, 10:13

Тыща заданий разом - это, конечно, мрак

ну, это как бы ПРЕДЕЛЬНОЕ значение, а так подаваться будет штучек по 20 ))
Если количество заданий N очень сильно влияет на АЛГОРИТМ, то давай ограничим N <= 100.

Цитата AVA12 @ 19.02.20, 10:13

А каково количество возможных значений времени выполнения и штрафа?

тебя интересует, чему равняется T(max), C(max)? В условии об этом не сказано. ну, какое-то разумное значение. Ну, давай сделаем T(max) <= 20, C(max) <= 10. Ну, это число из логики какой-то.

Добавлено 19.02.20, 10:36
AVA12, т е задача НЕТРИВИАЛЬНАЯ, да?
мне даже подумалось, что здесь что-то совсем простое, просто я слишком слаб в алгоритмике, что не вижу элементарное решение...

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

AVA12 — Wed, 19 Feb 2020 10:13:39 +0000

AVA12: Тыща заданий разом - это, конечно, мрак. А каково количество возможных значений времени выполнения и штрафа? Если количество возможных комбинаций невелико, то можно построить список отношений (время_выплнения, штраф, количество_заданий, задания[]) и дальше уже колдовать над этим списком.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

prografix — Wed, 19 Feb 2020 10:01:33 +0000

prografix: В задачу не вникал, но похоже, что можно применить динамическое программирование.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

Pavia — Wed, 19 Feb 2020 09:27:46 +0000

Pavia: Открыть книгу про теорию игр и прочитать.

Станок выполняет задания со штрафом ожидания. Найти минимальный штраф

FasterHarder — Wed, 19 Feb 2020 08:23:13 +0000

FasterHarder: Всем хай! Сходу к делу!

Есть такая задачка.
В нулевой момент времени станку ОДНОВРЕМЕННО поставляют N заданий. Станок может в любой момент времени выполнять только одно задание (задание нельзя прервать, т е, если он начал им заниматься, то пока не закончит, к др.заданию переходить не может). На выполнение каждого задания станку требуется T времени (в часах). Также каждое задание имеет характеристику C (у.е.) - сумма штрафа, взимаемая за каждый час ожидания начала исполнения.
Нужно найти такой порядок исполнения заданий, чтобы итоговая сумма штрафов по всем заданиям оказалась минимальной. Получить эту мин.сумму штрафа, а также порядок исполнения заданий станком.
-------------------------------------------
На рис.показал пример + результаты работы.
___________________________.png (, : 1750)

Я хотел как бы узнать про алгоритм)
Мне казалось, что нужно подавать станку задания, имеющие макс.штраф - оказалось не так.
Строить граф (вершины - задания), причем полный, т к станок может от любого задания перейти в любое другое. А дальше, что и непонятно.
Сортировать задания по полям "Время выполнения" или "штраф", ну, ок, а что потом.
Получить какую-то целевую "функцию" по типу f(T, C), которая говорит, мол бери это задание следующим...

Или это NP-полная задача, т е нужен ПОЛНЫЙ перебор ВСЕХ возможных вариантов??
Кстати, кол-во заданий может быть велико (под 1 000).

Подскажите как быть-то?