Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 19.05.2022, 13:04   #1
Silver_561
Новичок
Джуниор
 
Регистрация: 19.05.2022
Сообщений: 1
Вопрос Сложная задача на С++

Из заготовки длиной L можно изготовить детали (ювелирные изделия) длины l1, l2,..., ln ценности С1, С2,…, Сn. Определить план распила заготовки, обеспечивающий максимальную суммарную ценность изготовленных деталей
Silver_561 вне форума Ответить с цитированием
Старый 19.05.2022, 13:15   #2
macomics
Участник клуба
 
Регистрация: 17.04.2022
Сообщений: 1,833
По умолчанию

Заготовка согнута в L, а вырезать надо выпрямленные l ювелирные изделия. Действительно сложно. Я надеюсь хотя бы С в порядке убывания.
macomics вне форума Ответить с цитированием
Старый 19.05.2022, 14:07   #3
Arigato
Высокая репутация
СуперМодератор
 
Аватар для Arigato
 
Регистрация: 27.07.2008
Сообщений: 16,219
По умолчанию

Цитата:
Сообщение от Silver_561 Посмотреть сообщение
Определить план распила
Актуальная задача, без распила нынче никуда
Arigato вне форума Ответить с цитированием
Старый 19.05.2022, 17:41   #4
ViktorR
Старожил
 
Регистрация: 23.10.2010
Сообщений: 2,304
По умолчанию

Полагаю, что можно перемножить, соответственно, длины на цены и отсортировать в порядке убывания.
Далее отбирать до тех пор, пока оставшаяся длинна от L не станет меньше следующей l[i].
Как-то так, ...
ViktorR вне форума Ответить с цитированием
Старый 19.05.2022, 18:10   #5
macomics
Участник клуба
 
Регистрация: 17.04.2022
Сообщений: 1,833
По умолчанию

Не выйдет:
Код:
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).

Последний раз редактировалось macomics; 19.05.2022 в 18:33.
macomics вне форума Ответить с цитированием
Старый 19.05.2022, 20:06   #6
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,285
По умолчанию

Кажется, задача не так проста:
Цитата:
L = 5

l = 4 C = 4.5
l = 3 C = 3
l = 2 C = 2
Удельная ценность выше у детали с длиной 4, но лучше сделать по одной детали длин 3 и 2.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Старый 19.05.2022, 20:20   #7
macomics
Участник клуба
 
Регистрация: 17.04.2022
Сообщений: 1,833
По умолчанию

Код:
{n = 1 + огрызок, l = 4, C = 4.5} total = 5.625
macomics вне форума Ответить с цитированием
Старый 19.05.2022, 20:54   #8
digitalis
Старожил
 
Аватар для digitalis
 
Регистрация: 04.02.2011
Сообщений: 4,536
По умолчанию

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

Последний раз редактировалось digitalis; 19.05.2022 в 21:02.
digitalis вне форума Ответить с цитированием
Старый 20.05.2022, 01:31   #9
challengerr
Участник клуба
 
Аватар для challengerr
 
Регистрация: 30.07.2008
Сообщений: 1,639
По умолчанию

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

"Тогда перебор всех возможных вариантов имеет временну́ю сложность O(2^N), что позволяет его использовать лишь для небольшого количества предметов" ru.wikipedia.org/wiki/Задача_о_рюкзаке
"SPACE.THE FINAL FRONTIER.This's a voyage of starship Enterprise. It's 5-year mission to explore strange new worlds,to seek out new life and civilizations,to boldly go where no man has gone before"

Последний раз редактировалось challengerr; 20.05.2022 в 01:35.
challengerr вне форума Ответить с цитированием
Старый 20.05.2022, 13:57   #10
сфинкс
Форумчанин
 
Аватар для сфинкс
 
Регистрация: 17.06.2012
Сообщений: 954
По умолчанию

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

например для 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
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую

Последний раз редактировалось сфинкс; 20.05.2022 в 14:35.
сфинкс вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Сложная задача maksim96chic Помощь студентам 0 14.02.2015 01:03
Сложная задача Twixs Общие вопросы C/C++ 3 14.04.2014 15:40
VBA Код сложная задача.. Slavatron1984 Microsoft Office Excel 4 01.09.2013 21:41
задача на вид сложная erik2 Microsoft Office Excel 3 21.02.2011 01:16
С++ Сложная задача sir.andrey Помощь студентам 12 26.10.2010 20:25