|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
20.05.2022, 14:38 | #11 |
Высокая репутация
СуперМодератор
Регистрация: 27.07.2008
Сообщений: 15,547
|
Код:
E-Mail: arigato.freelance@gmail.com
Последний раз редактировалось Arigato; 20.05.2022 в 14:43. |
20.05.2022, 17:05 | #12 |
Форумчанин
Регистрация: 17.06.2012
Сообщений: 957
|
продолжая сообщение №10 ещё 5-минутный этюд
в отличие от многих программ формирует массивы сам чему пора посвятить отдельную тему: массивы случайных на разных ЯП а пока в qb64 qbasic назначаются длины и стоимости и случайно перемешав номера вместо перебора вводятся пока макс длину не превысят и считает суммы и естественно недоделано зато считает всё само без унижения пользователя вводом цифр в 21 веке Код:
и немного исследуя: перемешивает без повтора на 50-й раз поэтому все сразу додумывайте как переставлять неслучайно пример работы N = 7: L = 5 Код:
а здесь засим всё автор темы указал с++? сможет переделать из бэйсик и тему прочитают внезапно многие ... не только автор ввод из файла недопустим в онлайн компиляторы поэтому только синтез случайных или заданных не унижает
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую
Последний раз редактировалось сфинкс; 20.05.2022 в 17:35. |
20.05.2022, 17:29 | #13 |
Высокая репутация
СуперМодератор
Регистрация: 27.07.2008
Сообщений: 15,547
|
Автор же указал язык C++, зачем здесь нужен Бейсик?
Ввод из стандартного потока легко может быть перенаправлен из файла. E-Mail: arigato.freelance@gmail.com
|
20.05.2022, 22:47 | #14 |
Старожил
Регистрация: 04.02.2011
Сообщений: 4,550
|
"Бесик - это наше всё!" - сказал сами_знаете_кто
Полным перебором - тут много ума не надо. Но для больших чисел он очень затратен по времени выполнения. А вот решить "по-учёному"... Я приводил ссылку на метод динамического программирования, но если честно - сам его в данном применении не очень понял. Динамическим программированием поиск кратчайшего пути - приходилось решать, а тут что-то не въезжаю. Последний раз редактировалось digitalis; 20.05.2022 в 23:09. |
20.05.2022, 23:26 | #15 |
Форумчанин
Регистрация: 17.06.2012
Сообщений: 957
|
другой вариант: двоичный 2-ичный
вещь либо взяли либо не взяли поэтому комбинаций 2^N и для N=5: 2^N=32 вместо N!=120 синтезируем произведения цены и длины то бишь интегралы вновь только я пишу про интеграл все варианты сравниваем с теми у кого длина менее заданной и моя программа выше уже заполняет массивы и остаётся перейти в 2-ичные массивы через 5 минут: Код:
Код:
оглавление: http://rosettacode.org/wiki/Knapsack_problem long read: http://rosettacode.org/wiki/Knapsack_problem/0-1 Исходное условие цитата: "Из заготовки длиной L можно изготовить детали (ювелирные изделия) длины l1, l2,..., ln ценности С1, С2,…, Сn. Определить план распила заготовки, обеспечивающий максимальную суммарную ценность изготовленных деталей" и даже если мечтают делить в моей программе выдающей результаты изменится 1 символ с * на / специально где не сообщаю и мне больше интересны все перестановки 0 и 1 чтобы составить шифры и то в принципе понятно осталось выразить короче даже если решается другая задача
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую
Последний раз редактировалось сфинкс; 21.05.2022 в 13:33. |
21.05.2022, 12:08 | #16 |
Старожил
Регистрация: 04.02.2011
Сообщений: 4,550
|
С виду - такое наукообразное, сразу и не скажешь, что фигня. Опять "произведение" ... Включить голову и спросить себя: что оптимальнее - отрезать кусок 1м ценой 100$ или 2м ценой 100$ ? Даже бабка с рынка с 4-мя классами ответит: конечно, первый вариант. Деньги те же, а в куске останется больше.
Может быть, на Бесике оно как-то по другому... А вообще мне немного смешно: взяв наперевес курс информатики 8-го класса решать в лоб задачи, над которыми бились десятилетиями учёные мирового уровня, например https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ Ну для 5..10 вариантов полный пребор ещё рулит, ну а как десятки-сотни - это уже не лаба-курсач, а диссертовина. Хотя конечно - современными Гигагерцами-Терабайтами можно в лоб решать задачи, которые раньше требовали напряжения ума. --------------------------- Нам в Физтехе на АЯиЧМП ак. Моисеев Н.Н. рассказывал: когда в журнале было опубликовано сообщение об МВиГ - журнал был зачитан до дыр. И удивлялись: мы же это уже применяли не раз. Но вот сформулировать в виде метода додумалитсь только эти ребята. Последний раз редактировалось digitalis; 21.05.2022 в 12:22. |
21.05.2022, 13:38 | #17 |
Форумчанин
Регистрация: 17.06.2012
Сообщений: 957
|
допустим делим на ценность и получаем дробные
и заодно улучшил шифры добавив всегда начальные нули Код:
Код:
поэтому лучше умножать на ценность то бишь интегрировать и заодно программа короткая и понятная даже школьникам данный мой оригинальный алгоритм не жадный плюс оглавление про рюкзак на разных ЯП http://rosettacode.org/wiki/Knapsack_problem
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую
Последний раз редактировалось сфинкс; 21.05.2022 в 16:17. |
21.05.2022, 15:54 | #18 |
Участник клуба
Регистрация: 17.04.2022
Сообщений: 1,833
|
Задумайтесь вот о чем. Решать задачу с помощью жадного алгоритма можно, но он не эффективен, если в результате его работы остался остаток, хотя его разбиение является максимально эффективным для разбитого отрезка. Тогда у нас остается отрезок длинной r и искать динамическим программированием надо не все разбиение, а только для конца отрезка меньшей длины. За исходное разбиение можно принять то, что дал жадный алгоритм, прибавляя к нему по кусочку и выполняя динамическим программированием разбиение маленького кусочка с меньшей длиной чем (n - i) * max(l / C) (i = НОД(max(l / C), min(l /C))).
Таким образом перебор и расход памяти в динамическом методе будет минимальным, а при полном разбиении жадным алгоритмом и вовсе не понадобится. |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Сложная задача | 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 |