Публикации по теме 'knapsack-problem'
Волшебное приключение с рюкзаком: Руководство для начинающих по задаче о рюкзаке!
Добро пожаловать, юный искатель приключений! В очаровательном мире информатики вас ждет захватывающее приключение, известное как «Задача о рюкзаке». Представьте, что вы отважный герой с волшебным рюкзаком. Ваша миссия? Наполнить этот мистический рюкзак сокровищами, каждое со своей ценностью и весом. Но будьте осторожны! Ваш рюкзак имеет ограниченную грузоподъемность, и вы должны мудро выбирать сокровища, чтобы максимизировать свою добычу. Не бойтесь, мы раскроем тайны динамического..
В поисках правильного импульса
В поисках правильного импульса
Насколько полезна линейность для подсчета массивных случаев.
Иногда нас интересует обзор всей системы как более целостная точка зрения. Эта точка зрения порождает общие впечатления, побуждающие нас делать то или иное дело. Однако эти импульсы производятся после первого обзора всей окружающей среды, чтобы прийти к очень сложным выводам.
В этом посте я покажу механизм, который поможет нам понять, как находить десятки взаимосвязанных проблем и как с..
Решение задачи о рюкзаке оптимизации доходов на практике
Решение задачи о рюкзаке оптимизации доходов на практике
Напомним, что, как упоминалось в предыдущем посте , Onera может превратить задачу оптимизации доходов без ухудшения качества обслуживания клиентов в следующую задачу о рюкзаке. В частности, мы имеем следующую постановку задачи:
В приведенной выше формулировке розничный продавец продает набор товаров I. Каждый элемент i в I имеет значение v ( i ), которое является ожидаемым доходом ( или маржа), которую розничный..
Вопросы по теме 'knapsack-problem'
Каков хороший алгоритм сжатия записей в заблокированном файле?
Предположим, у вас есть большой файл, состоящий из группы блоков фиксированного размера. Каждый из этих блоков содержит некоторое количество записей переменного размера. Каждая запись должна полностью помещаться в один блок, и тогда такие записи по...
1004 просмотров
schedule
20.11.2022
Улучшенный генетический алгоритм для задачи с несколькими рюкзаками
Недавно я улучшал традиционный генетический алгоритм для задачи с несколькими рюкзаками. Итак, мой улучшенный генетический алгоритм работает лучше, чем традиционный генетический алгоритм. Я тестировал. (я использовал общедоступный из OR-Library (...
553 просмотров
schedule
21.12.2022
Как мне решить MKP с линейным программированием?
Я изучаю проблему ранца. Так что я тут одного не понимаю.
Соотношение прибыль/псевдоресурсопотребление
U j = P j / W j , где W j = R ji * А j
Я надеюсь, что вы, люди, знаете это уравнение, поэтому я думаю, что нет необходимости в...
479 просмотров
schedule
01.10.2022
Проблема с раскроем запаса
Кто-нибудь знает, как реализовать алгоритм для этой задачи с помощью алгоритма Knapsack?
Метод, который я сейчас использую, широко использует LINQ, коллекции коллекций и несколько словарей. Для тех, кто не понимает, о чем я говорю, прочтите...
2733 просмотров
schedule
20.03.2022
Алгоритм, представляющий собой комбинацию задачи непрерывного рюкзака и задачи упаковки контейнеров переменного размера.
Пытаюсь решить задачу (на php, но язык программирования не имеет значения). У меня есть n количество человек, которые заплатили деньги, и у меня есть m количество людей, которые собираются заплатить ту же сумму, что и сумма того, что n...
1282 просмотров
schedule
28.06.2023
JaCoP: Решение проблемы с рюкзаком 0/1
Я пытался научиться использовать библиотеку программирования ограничений JaCoP, но у меня возникли некоторые трудности с реализацией задачи о рюкзаке 0/1. Я попробовал размер задачи 4 и определил элементы и переменные следующим образом:...
1488 просмотров
schedule
31.08.2022
Задача о ранце со всей прибылью, равной 1
Существует разновидность задачи о ранце, когда все прибыли равны 1. Кажется, ее можно решить намного быстрее, чем классическую дискретную (0-1) задачу о ранце, но как? Будет ли работать просто жадный алгоритм (на каждой итерации класть в рюкзак...
1388 просмотров
schedule
11.06.2023
Почему задача о рюкзаке псевдополиномиальна?
Я знаю, что Knapsack является NP-полным, хотя он может быть решен с помощью DP. Они говорят, что решение DP равно pseudo-polynomial , поскольку оно экспоненциально по «длине ввода» (то есть количеству битов, необходимых для кодирования ввода). К...
36838 просмотров
schedule
10.08.2023
задача о рюкзаке (классика)
Итак, я должен решить задачу о рюкзаке для класса. Пока что я придумал следующее. Мои компараторы - это функции, которые определяют, какой из двух предметов будет лучшим вариантом (путем просмотра соответствующих кортежей (значение, работа)).
Я...
4769 просмотров
schedule
23.09.2023
Логическая форма получения минимальной верхней границы для данного числа из набора чисел
Моя проблема заключается в следующем-
У меня есть несколько номеров, как показано ниже:
2
2
2
2
3
3
17
17
17
17
17
17
17
17
17
34
34
34
34
34
68
68
68
136
Итак, если я даю следующее число в качестве входных...
96 просмотров
schedule
21.08.2023
жадный множественный рюкзак (минимизировать/уменьшить количество корзин)
на самом деле, у меня уже есть частичный ответ на этот вопрос, но мне интересно, можно ли этот небольшой фрагмент жадного кода обобщить до чего-то более близкого к оптимальному решению.
как я столкнулся с этой проблемой (не относится к самой...
857 просмотров
schedule
27.05.2022
C # 0-1 Задача о ранце с известной суммой и количеством нулей в наборе
У меня есть таблица значений 5x5 от 0 до 3 включительно со всеми неизвестными значениями. Я знаю как сумму значений, так и количество нулей для каждой строки и столбца. Как я могу решить эту задачу с рюкзаком 0-1 с помощью C # и получить возможные...
1853 просмотров
schedule
15.02.2023
Генерация набора мощности списка
Мне нужно написать грубую реализацию задачи о рюкзаке. Вот псевдокод:
computeMaxProfit(weight_capacity)
max_profit = 0
S = {} // Each element of S is a weight-profit pair.
while true
if the sum of the weights in S <=...
2906 просмотров
schedule
18.02.2023
Динамическое программирование рюкзака
это типичная задача о рюкзаке, требующая динамического программирования, и нет ограничений на поставку предметов. Я работал над этим для своего класса, я пытался часами поиграть с алгоритмом, но все еще не дошел.
public static int...
1825 просмотров
schedule
23.09.2022
Сумма динамического программирования
Как бы вы использовали динамическое программирование, чтобы найти список положительных целых чисел в массиве, сумма которых ближе всего к некоторому положительному целому числу K, но не равна ему?
Я немного застрял, думая об этом.
2428 просмотров
schedule
08.03.2023
Извлечение предметов из рюкзака с помощью динамического программирования
Я новичок в динамическом программировании и попробовал свою первую проблему DP. Постановка проблемы
Учитывая рюкзак размера C и n предметов размеров s[] со значениями v[], максимизируйте вместимость предметов, которые можно положить в рюкзак....
2075 просмотров
schedule
13.10.2022
C++ реализация ранцевой ветки и привязки
Я пытаюсь реализовать С++ эту проблему с рюкзаком, используя ветвь и ограничение. На этом веб-сайте есть версия Java: Реализация ветки и привязка к рюкзаку
Я пытаюсь заставить свою версию C++ распечатать 90, которые она должна, однако она этого...
24327 просмотров
schedule
26.04.2023
Рюкзак - Как определить, какие веса используются?
У меня есть код, который дает максимальное значение, которое я могу получить, заполнив рюкзак оптимальным набором гирь.
int arr[5] = {0, 0, 0, 0, 0};
int Weight[5] = {2, 5, 8, 7, 9};
int Value[5] = {4, 5, 7, 9, 8};
const int n = 5;
const int...
484 просмотров
schedule
27.11.2022
Попытка выяснить классическое повторение Knapsack
Я читаю о Knapsack Problem (unbounded), который, насколько я понимаю, является классикой в DP. Хотя я думаю, что понял решение, когда прочитал его, я не совсем понимаю, как я могу преобразовать его в реальный код. Например, в следующей «формуле»...
3210 просмотров
schedule
21.05.2022
сумма подмножества - нахождение максимальной суммы строго ниже m с размером подмножества k
Я борюсь со следующей проблемой: учитывая набор из n элементов, найдите максимальную сумму подмножества размера k, которое строго меньше и как можно ближе к заданному числу m.
Я решил проблему без ограничения, что подмножество должно иметь размер...
751 просмотров
schedule
10.10.2022
