Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности

Новые сообщения [новые:0]
Дайджест
Горячие темы
Избранное [новые:0]
Форумы
Пользователи
Статистика
Статистика нагрузки
Мод. лог
Поиск
|
|
10.06.2014, 15:12
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
Доброго времени суток C: Модератор: Лишнее удалено У нас есть k мешков, каждый мешок вмещает определённое количество килограммов. У нас есть n кирпичей, каждый имеет вес. Как заполнить все мешки до упора, если это возможно. Каждый кирпич может быть только в одном мешке. Я придумал два алгоритма решения данной задачи. Второй более длинный, но мне он пока более интересный. Прикладываю часть кода написанного на листке (ибо почему-то стали болеть глаза, и я сначала пишу код на листке). Сейчас стал его набирать, и возникли проблемы при выделении памяти на массив структур. Видимо такой тип структур нужно сразу инициализировать ? Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. Можно ли исправить мой алгоритм малой кровью ? Пожалуйста не решайте её за меня (а если вам самим будет интересно, то поместите код в раскрывающийся знак плюса, пожалуйста) Модератор: Вложение удалено. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2014, 15:14
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
Всё-же наберу код. Мне кажется не очень хорошо будет видно ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2014, 15:23
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
Код: plaintext 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. PS Я понимаю что этот алгоритм на оптимальный, в голове у меня есть более быстрый вариант ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2014, 15:27
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
SashaMercuryВот задача в моём понимании: У нас есть k мешков, каждый мешок вмещает определённое количество килограммов. У нас есть n кирпичей, каждый имеет вес. Как заполнить все мешки до упора, если это возможно. Каждый кирпич может быть только в одном мешке. Во-первых, кирпичи не сыпучие, заполнить ими мешок до полной вместимости чисто технически невозможно. Во-вторых, если суммарная вместимость мешков Х, а общий вес кирпичей Y, причём X >> Y, то заполнить все мешки не получится точно так же технически. Из чего следует вывод, что у тебя какое-то неправильное понимание задачи. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2014, 15:35
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
Вот пример: три мешка 10, 15, 120 кг. Кирпичи: 3,12,105,15,16,4,3,3 1 мешок 4+3+3 2 3+12 3 сделать нелья На выходе - пустое множество или что-нибудь. Если суммарная масса мешков больше кирпичей тоже самое на выходе пусто, я же указал в постановке-"если это возможно". Если невозможно меня не интересует, очевидно это можно проверить. Мешки и кирпичи абстракция, постановка задачи совершенно другая, так просто проще объяснить было ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2014, 15:36
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
Ой, третий можно, да ещё двумя способами. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2014, 15:40
|
|||
|---|---|---|---|
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
Даже если не заморачиваться на тему "сколько килограмм в литре", условие задачи непонятно. Какая целевая функция? Как сравнить какое из двух решений лучше? Например: 4 мешка заполнено на 80% или три на 90% + один на 50%? что лучше? Сформулируй и напиши функцию сравнения двух решений. PS По сути это задача о рюкзаке, только рюкзаков больше одного. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2014, 15:41
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
SashaMercuryВот пример: три мешка 10, 15, 120 кг. Кирпичи: 3,12,105,15,16,4,3,3 Вот это - практически классическая задача рюкзака. Но всё же придётся определить цель: разложить вещи в минимальное число мешков или разложить вещи по всем имеющимся мешкам как можно равномернее. Или просто ответить на вопрос "влезет или нет". В зависимости от цели способы решения будут разные. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2014, 16:00
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
Каждый рюкзак должен быть заполнен на 100 процентов. 99 процентов не интересны. Нужно узнать как именно будут распределны кирпичи по мешкам. Не все кирпичи обязательно использовать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2014, 16:02
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
SashaMercuryКаждый рюкзак должен быть заполнен на 100 процентов. 99 процентов не интересны. Нужно узнать как именно будут распределны кирпичи по мешкам. Не все кирпичи обязательно использовать. Тогда не парься и делай полный перебор. Для малого количества кирпичей сойдёт. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2014, 16:38
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
Вопросы по данному конкретному алгоритму, что я привел...там и есть полный перебор, вариация..точней вопросы по-реализации алгоритма, я ведь привел свой код. Меня гонят .. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2014, 17:13
|
|||
|---|---|---|---|
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
On 10.06.2014 16:12, SashaMercury wrote: > У нас есть k мешков, каждый мешок вмещает определённое количество > килограммов. У нас есть n кирпичей, каждый имеет вес. Как заполнить все > мешки до упора, если это возможно. Каждый кирпич может быть только в > одном мешке. Это какая-то вариация на дискретную задачу о рюкзаке, которая является каноническим примером NPполной задачи. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
10.06.2014, 17:24
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
SS-phoneВопросы по данному конкретному алгоритму, что я привел...там и есть полный перебор, вариация..точней вопросы по-реализации алгоритма, я ведь привел свой код. Выкинь этот алгоритм вместе с вопросами по нему, он дохлый. Лично я бы попробовал рекурсию. В конце концов заполнение мешка размера n это заполнение остатками кирпичей мешка размера n-x в котором уже лежит один кирпич размера х. Точно так же как и заполнение остатками кирпичей k-1 мешков после заполнения первого. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.06.2014, 01:34
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
Dimitry Sibiryakov Выкинь этот алгоритм вместе с вопросами по нему, он дохлый. Почему дохлый ? Он работает теоретически. Осталось решить проблему со структурой, и доделать вторую часть программы с пересечением. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.06.2014, 02:11
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
Алгоритм находит для каждого мешка все удовлетворяющие комбинации кирпичей, и записывает их в массив. 2 часть-найти непересекающиеся комбинации. Проблема только в массиве, и она обозначена в первом сообщении. PS Я знаю что можно короче. Сначала хочу сделать так. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.06.2014, 10:36
|
|||
|---|---|---|---|
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
SashaMercuryDimitry Sibiryakov Выкинь этот алгоритм вместе с вопросами по нему, он дохлый. Почему дохлый ? Он работает теоретически. Осталось решить проблему со структурой, и доделать вторую часть программы с пересечением. как бы хочу напомнить, что работать в данном случае может только алгоритм с полным перебором всех комбинаций. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.06.2014, 11:09
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
Так я и перебираю все комбинации ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.06.2014, 16:18
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
SashaMercuryПочему дохлый ? Назовём это "интуицией разработчика". Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.06.2014, 17:24
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
Мне кажется, с большой долей вероятности, интуиция иногда ошибается :-). Я допишу этот алгоритм и покажу вам. Но было бы-лучше побольше конкретики, что вам не нравится. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
11.06.2014, 23:14
|
|||
|---|---|---|---|
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
SashaMercuryМне кажется, с большой долей вероятности, интуиция иногда ошибается :-). Я допишу этот алгоритм и покажу вам. Но было бы-лучше побольше конкретики, что вам не нравится. Спешу заметить, друг что в самом творческом процессе коим и является "писание программ" или "синтез" своих алгоритмов, практически нет никакой конкретики. Творчество - не детерминировано, изначально интуитивно и не раскладывается ни в какие формы или каноны. И сейчас ты занимаешся самым что ни на есть творчеством. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.06.2014, 16:09
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
Спасибо, это конечно здорово звучит. Творчество. Жаль что только у меня мало кисточек. Вообщем, несмотря на пять часов сна из-за Бразилии в 7 утра, я сделал что-то полезное. В последние дни у меня в голове крутится проблема с пересечением множеств разных мощностей, и пока я не решил её. Но я нахожу для каждого мешка все возможные комбинации. Мне части моего когда кажутся порнографией если честно, выделяю слишком много лишней памяти. Вот что пока получилось. И это работает. Осталось только пересечение найти.. Код: plaintext 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. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.06.2014, 16:34
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
Я только что придумал как сделать пересечение. Берём массив F. Помещаем в него все подходящие комбинации первого массива. Последовательно сравниваем элементы F со элементами 2 мешка. Если попарно всё ок, то перезаписываю F элементами a1|a2, далее F сравниваю с комбинациями 3 мешка, и т.д. Только надо хранить для каждого элемента F историю. Да это не просто, но мы видим что решение есть. Всё, замыпаю. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.06.2014, 16:44
|
|||
|---|---|---|---|
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
SashaMercury, на всякий случай напомню что комбинаторика РАЗЛИЧАЕТ следующие понятия сочетания перестановки размещения и когда ты в тексте используешь термин из К. то нужно говорить точными понятиями. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
14.06.2014, 16:58
|
|||
|---|---|---|---|
|
|||
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
Просто я не считаю что использую термины из комбинаторики. Ну да ладно. Сегодня вечером подумал, и сделал такую структуру для хранения 1. Побитового или всех комбинаций текущего набора. 2. Реальной мощности данного набора 3. Массива из k элементов, каждый элемент есть набор для каждого мешка. Пока вот такой код: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. PS Видел сегодня Скиену- Алгоритмы. Стоит покупать ? или лучше начать с Кнута ? Я просто помню что кто-то мне эту книгу советовал. Или где я встречал эту фамилию совсем недавно.. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
15.06.2014, 11:28
|
|||
|---|---|---|---|
Мешки и кирпичи. Проблемы в реализации |
|||
|
#18+
SashaMercuryPS Видел сегодня Скиену- Алгоритмы. Стоит покупать ? или лучше начать с Кнута ? Я просто помню что кто-то мне эту книгу советовал. Или где я встречал эту фамилию совсем недавно.. Скачай, посмотри, а там решишь что тебе больше понравится. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|

start [/forum/topic.php?fid=57&mobile=1&tid=2019418]: |
0ms |
get settings: |
10ms |
get forum list: |
13ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
76ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
57ms |
get tp. blocked users: |
1ms |
| others: | 277ms |
| total: | 452ms |

| 0 / 0 |
