Описание тега knapsack-problem
Проблема рюкзака - это проблема комбинаторной оптимизации: по заданному набору элементов с соответствующими весами и значениями определить количество каждого элемента, которое нужно включить в коллекцию, чтобы общий вес был меньше или равен заданному пределу и максимизировал Общая стоимость. Это NP-полная проблема, но несколько общих упрощений эффективно решаются с помощью динамического программирования.
1
ответ
Минимизация цветов: вариация алгоритма ранца?
Работая над проектом, я столкнулся с этой проблемой, которую я перефразирую здесь в терминах, выходящих за пределы реальной области проблемы (я полагаю, я мог бы поговорить о калибрах фейерверков и форм, но это усложнит понимание). Я ищу (возможно, …
20 апр '12 в 10:52
1
ответ
Любой псевдополиномиальный алгоритм для ограниченного 0-1 мультиранпака?
Предположим, что существует n элементов, например, i1, i2,.... in, каждый из которых имеет известный ограниченный вес w1, w2,... wn. Есть также набор из рюкзаков, например, k1, k2 и km. Рюкзаки однородны, так как все они имеют одинаковую вместимость…
14 апр '13 в 13:40
0
ответов
Рюкзак динамический в R
Я пытаюсь реализовать код sudo из википедии, чтобы решить проблему ранца, но мой код не работает. Моя функция принимает в качестве входных данных фрейм данных X с 2 столбцами, первый был весами, а второй значения weights value 10 110 20 150 15 180 3…
12 окт '18 в 09:17
1
ответ
Оптимальная линейка MLB с использованием варианта рюкзака
Я пишу программу, чтобы найти наилучшую возможную линейку MLB, используя рюкзак. Для этого я передаю данные об игроках, в которых рассчитана стоимость игрока и зарплата. Заработная плата будет моим "весом" с точки зрения того, чтобы быть проблемой р…
29 сен '15 в 20:47
5
ответов
Разделение списка значений на три равных промежуточных итога
У меня есть список чисел, которые в общей сложности 540000. Я хотел бы отсортировать этот список на 3 списка, каждый из которых составляет 180000. Каков наиболее эффективный метод программирования, чтобы сделать это, предполагая, что список чисел пр…
06 ноя '09 в 10:32
1
ответ
Что-то не так с моим массивом идентификаторов?
Эта программа извлекает два столбца из файла input.txt, где первый столбец указывает значение объекта, а второй столбец представляет вес. Значения импортируются и помещаются в два массива: массив значений и массив весов. Расчеты ранца сделаны. Всего…
02 ноя '16 в 19:34
1
ответ
Зачем менять местами порядок рюкзаков на то же решение?
Насколько я знаю, в проблеме ранца используется динамическое программирование, чтобы найти лучшее решение для каждого элемента в зависимости от его предыдущих элементов. Эта гипотеза предполагает, что решение зависит от порядка элементов. Почему око…
24 май '17 в 02:40
1
ответ
Рюкзак (многокритериальный)
Если у меня есть рюкзак, где вес w имеет два значения v1 и v2, а емкость равна m. Как я найду общие значения для v1 и v2, где вес не превышает емкость m?
16 авг '12 в 15:28
1
ответ
Рюкзак с весом и лимитом предметов
Если у меня есть рюкзак с ограничением веса W, пункт Limit K и у меня есть N элементов, N >= k Я знаю, как максимизировать его, имея массив трехмерного запоминания m[N][W][K] (N элементов для рассмотрения, W оставленный вес, K элементов для выбора) …
22 апр '14 в 14:09
1
ответ
Как создать отчет о огурце, если я использую рюкзак
Я параллельно выполняю тесты в своей работе с конвейером jenkins, используя рюкзак. Мне нужен JSON отчет после работы для плагина Cucumber Reports. Теперь я бегу огурец, как: bundle exec rake knapsack:cucumber Но для плагина мне нужно запустить огур…
12 июл '17 в 07:29
2
ответа
Сумма подмножества чисел
Скажем, у меня есть одно число 'n' и таблица чисел. Я хочу выбрать до четырех чисел в таблице, и сумма этих четырех будет максимально приближенным к n. Учитывая длину 'L' таблицы, количество комбинаций, которые она должна пройти, равно (6*L + 11*L^2…
26 мар '13 в 19:24
1
ответ
Почему существует необходимость приблизительного решения для 0-1 ранца, если входные значения высоки?
В Geeks for Geeks Link упоминается, что "если входные значения высоки, то решение для 0-1 ранца становится недостижимым, и существует необходимость приблизительного решения". И в приближенном решении, т.е. решении FPTAS, значения, соответствующие ве…
09 янв '19 в 13:53
0
ответов
Умный алгоритм раскола ранца
Предположим, мы должны заполнить мешок предметами, основанными на разделении Threshold. Нужно взять минимальные значения мешка, чтобы заполнить все предметы. Пример: когда емкость мешка (порог) установлена на 15 кг: Элемент 1: 10 кг Элемент 2: 8 к…
22 ноя '17 в 04:50
1
ответ
Как добавить ограничения в линейное программирование задачи о ранце в R?
Я работал с кодом, найденным по адресу: https://sites.math.washington.edu/~conroy/2015/m381-aut2015/Rexamples/knapsack.r Мне было интересно, если кто-нибудь знает, как добавить условное ограничение, которое учитывает только определенное количество п…
11 фев '19 в 01:48
2
ответа
Обнаружение пробелов в сетке div
РЕДАКТИРОВАТЬ Решение было найдено! Вот пост в блоге об этом, а вот репозиторий Github! Я работаю над созданием сетки div, состоящей из блоков разных размеров, эти размеры устанавливаются по высоте и ширине, но генерируются динамически, поэтому при …
04 дек '12 в 14:45
2
ответа
Код рюкзака - не работает в некоторых случаях
Мой код выглядит следующим образом: #include<stdio.h> int max(int a,int b) { return a>b?a:b; } int Knapsack(int items,int weight[],int value[],int maxWeight) { int dp[items+1][maxWeight+1]; /* dp[i][w] represents maximum value that can be a…
25 дек '13 в 08:25
2
ответа
Алгоритм ранца с дополнительным свойством
Когда есть 1 собственность, я понимаю, что там происходит. У меня проблема с пониманием проблемы рюкзака, когда существует более 1 свойства. Я должен написать программу, которая использует алгоритм ранца с 2 свойствами. Учитель сказал нам, это должн…
19 ноя '12 в 07:01
0
ответов
Оптимизация муравьиных колоний на 01 МКП
Я пытаюсь реализовать ACO для 01MKP. Мои входные значения взяты из библиотеки OR mknap1.txt. Согласно моему алгоритму, сначала я выбираю предмет случайным образом. Затем я вычисляю вероятности для всех других элементов на строительном графике. уравн…
18 апр '12 в 19:39
1
ответ
Рекурсивный рюкзак Java
Я борюсь с домашним заданием и считаю, что сильно усложняю решение и нуждаюсь в помощи от любого, кто захочет его предложить. Позвольте мне объяснить некоторые основные правила для этого задания. Ниже приведена ссылка на другой пост, в котором есть …
10 окт '13 в 00:23
2
ответа
Можно использовать задачу о ранце с указанным количеством весов
У меня проблема с рюкзаком с указанным объемом рюкзака по весу и весу. Мне нужен алгоритм, который упаковывает веса в рюкзак, когда вместимость ранца равна C, необходимое количество весов равно N, и есть список весов. Сортировка весов не имеет значе…
27 мар '11 в 19:44