Сложная задача на С++

[Silver_561]

Из заготовки длиной L можно изготовить детали (ювелирные изделия) длины l1, l2,..., ln ценности С1, С2,…, Сn. Определить план распила заготовки, обеспечивающий максимальную суммарную ценность изготовленных деталей

[macomics]

Заготовка согнута в L, а вырезать надо выпрямленные l ювелирные изделия. Действительно сложно. Я надеюсь хотя бы С в порядке убывания.

[Arigato]

Сообщение от Silver_561

Определить план распила

Актуальная задача, без распила нынче никуда

[ViktorR]

Полагаю, что можно перемножить, соответственно, длины на цены и отсортировать в порядке убывания.
Далее отбирать до тех пор, пока оставшаяся длинна от L не станет меньше следующей l[i].

[macomics]

Не выйдет:

L = 10; lC1 = {5, 49}, lC2 = {3, 17}, lC3 = {1, 10}.

Ответ:

{n = 10, l = 1, C = 10} total = 100.

Остальные решения:

{n = 2, l = 5, C = 49} total = 98
{n = 1, l = 5, C = 49} + {n = 1, l = 3, C = 17} + {n = 2, l = 2, C = 10} total = 86
{n = 1, l = 5, C = 49} + {n = 5, l = 1, C = 10} total = 99
{n = 3 l = 3, C = 17} + {n = 1, l = 1, C = 10} total = 61
{n = 2, l = 3, C = 17} + {n = 4, l = 1, C = 10} total = 74
{n = 1, l = 3, C = 17} + {n = 7, l = 1, C = 10} total = 87.

Достаточно C / l, отсортировать массив полученных значений в порядке убывания и выполнить разбиение L на l`1 элементов, остаток L на l`2 и т.д. пока остаток L > любого из оставшихся l` (l` элементы в порядке массива C / l).

[BDA]

Кажется, задача не так проста:

L = 5

l = 4 C = 4.5
l = 3 C = 3
l = 2 C = 2

Удельная ценность выше у детали с длиной 4, но лучше сделать по одной детали длин 3 и 2.

[macomics]

{n = 1 + огрызок, l = 4, C = 4.5} total = 5.625

[digitalis]

Классическая "задача о ранце (рюкзаке)". Целочисленное решение может сильно отличаться от полученного методом #4. Но наука уже решила этот вопрос Вот один из вариантов (динамическое программирование) .
https://skillbox.ru/media/code/dinam...hu_o_ryukzake/
И в варианте #4 нужно было не умножать, а делить: денег чтоб больше, а отрезать чтоб меньше.

[challengerr]

Задача на полный перебор... ru.wikipedia.org/wiki/Полный_перебор

"Тогда перебор всех возможных вариантов имеет временну́ю сложность O(2^N), что позволяет его использовать лишь для небольшого количества предметов" ru.wikipedia.org/wiki/Задача_о_рюкзаке

[сфинкс]

количество перестановок всех элементов: факториал

например для N=5 N!=120

получив все перестановки получим все стоимости

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

перестановки программно практически: циклы и проверка на повтор
и подобное решалось в моих сообщениях про ребус из букв

специально в конце страницы чтоб прочитали поменьше
прикольная программа 5-минутка
составляет сочетания всех цифр числа разряда N
практически номера элементов

N = 5: a = 10 ^ N: la = Len(Str$(a)): s = 0 'perestan.bas
For b = a To 1 Step -1: b$ = Str$(b): lb = Len(b$): bb$ = Mid$(b$, 2, lb)

    For c = 1 To la - lb - 1: b$ = "0" + bb$: Next

    For i = 1 To la - 1: For j = i + 1 To la
        If Mid$(b$, i, 1) = Mid$(b$, j, 1) Then GoTo 5
    Next: Next

    s = s + 1: Print s, b
5 Next