Публикации по теме 'knapsack-problem'
Модифицированный генетический алгоритм для решения задачи о рюкзаке с нулевой единицей
Эта статья является третьей частью моей предыдущей статьи: Генетические алгоритмы решения задачи о рюкзаке с нулевой единицей . Пожалуйста, прочтите эту статью, прежде чем переходить к этой статье, чтобы лучше понять концепцию. Во второй статье серии рассказывается о реализации традиционного генетического алгоритма для задачи о рюкзаке ноль-единица, прочтите эту статью здесь .
В этой статье мы поговорим об модифицированном генетическом алгоритме, который вдохновлен двумя вариантами..
Раскрытие проблемы неограниченного рюкзака
Задача неограниченного рюкзака — важная подтема динамического программирования, имеющая важные применения в соревнованиях по алгоритмам и собеседованиях.
Описание проблемы следующее:
Есть n ( n <= N ) предметов и рюкзак вместимостью m ( m <=M ). Каждый предмет имеет бесконечное количество. Вес и стоимость i-го предмета равны w[i] и v[i] соответственно.
Теперь нам нужно выбрать некоторые предметы, чтобы положить их в рюкзак, и общая вместимость не может превышать..
Оптимизация решения динамического программирования задачи о рюкзаке для пространственной сложности
Ранее я писал о решении пары вариантов задачи о ранце с помощью динамического программирования ( ДП ). Если вы их не читали или вам нужно освежить память, вы можете проверить их здесь и здесь .
В этих решениях мы строим двумерный массив размером N * M (представляющий таблицу из N * M ячеек), где N - количество предметов, из которых мы можем выбрать, а M - количество единиц вместимости нашего рюкзака.
Сегодня я опишу, как эти решения можно оптимизировать для использования..
Проблема с рюкзаком
Различные методы решения задачи о рюкзаке
Решая задачи по динамическому программированию, я столкнулся с задачей о рюкзаке. Это одна из стандартных проблем, которую должен решить каждый программист. В этой статье я расскажу, что такое задача о рюкзаке и какие методы можно использовать для ее решения.
Учитывая вес и стоимость n предметов, положите эти предметы в рюкзак вместимостью W, чтобы получить максимальное общее значение в рюкзаке.
Другими словами, постановка задачи о рюкзаке..
Вопросы по теме 'knapsack-problem'
Алгоритм разделения списка чисел на 2 списка равных сумм
Есть список номеров.
Список должен быть разделен на 2 списка одинакового размера с минимальной разницей в сумме. Суммы должны быть напечатаны.
#Example:
>>>que = [2,3,10,5,8,9,7,3,5,2]
>>>make_teams(que)
27 27
Есть ли...
15669 просмотров
schedule
22.03.2023
Как обеспечить выполнение потоков Java на разных ядрах
Я пишу многопоточное приложение на Java, чтобы повысить производительность по сравнению с последовательной версией. Это параллельная версия решения динамического программирования для задачи о ранце 0/1. У меня Intel Core 2 Duo с Ubuntu и Windows 7...
14192 просмотров
schedule
07.03.2023
Реконструкция пути рюкзака 0-1 (какие предметы брать)
Я знаю, как решить проблему с рюкзаком 0-1 с помощью подхода динамического программирования, но у меня возникают проблемы с выяснением того, какие предметы брать, не ставя под угрозу сложность O (N * C) (N предметов, C вместимость).
Любые идеи (я...
3161 просмотров
schedule
07.07.2022
Рекурсивный возврат
У меня проблема с моей функцией возврата, она зацикливается с определенными данными. Я не могу написать здесь весь программный код, но могу поместить сюда свою функцию.
bool shareMoney(int quantity, int *values, int index, int moneyA, int half,...
2102 просмотров
schedule
14.05.2022
Эффективная таблица для динамического программирования на Haskell
Я написал проблему с рюкзаком 0-1 на Haskell. Я довольно горжусь ленью и уровнем общности, достигнутым до сих пор.
Я начну с предоставления функций для создания и работы с ленивой 2D-матрицей.
mkList f = map f [0..]
mkTable f = mkList (\i...
3741 просмотров
schedule
17.05.2022
Рюкзак с использованием GA
Я не спрашивал о задаче о рюкзаке с помощью генетического алгоритма. при инициализации я использую такой вид хромосомы [1] = [вес] [прибыль], потому что его формула КП по оценке хромосомы вес х прибыль. нет, после входа с помощью выбора колеса...
330 просмотров
schedule
22.01.2023
Алгоритм ранца для умножения
У меня есть набор N чисел с некоторой стоимостью, связанной с каждым числом, и проблема состоит в том, чтобы выбрать все возможные наборы чисел в виде списка, чтобы их произведение было меньше определенного числа M , отсортированного по сумме...
837 просмотров
schedule
07.04.2022
Рюкзак с минимальной стоимостью
У меня есть несколько типов монет, у каждой есть вес (wi) и стоимость (ci). Итак, мне нужно сделать рюкзак весом == W и (!) Минимальной стоимостью монет в нем. Я не могу сделать повторение использования DP.
2619 просмотров
schedule
09.12.2022
Ошибка в простом алгоритме динамического программирования (классический ранец)
Я просмотрел http://rosettacode.org/wiki/Knapsack_problem/0-1 , чтобы решить базовую задачу динамического программирования рюкзака, и я получил рабочее решение (рюкзак1()), но когда я попробовал другое решение (рюкзак2()), я почувствовал, что где-то...
222 просмотров
schedule
11.03.2023
0/1 Ранцевая оптимизация динамического программирования, переход от 2D-матрицы к 1D-матрице
Мне нужно некоторое разъяснение из Википедии: Рюкзак , со стороны
Таким образом, это решение будет работать за время O(nW) и пространство O(nW). Кроме того, если мы используем только одномерный массив m[W] для хранения текущих оптимальных...
10568 просмотров
schedule
20.06.2023
Почему этот алгоритм для целочисленного рюкзака неверен?
Это то, что я думаю, что мне нужно сделать.
Имея «n» предметов веса «Wi» и значения «Vi», мне нужно максимизировать стоимость рюкзака, оставаясь при этом ниже предела веса WEIGHT_MAX.
Итак, я подумал о том, чтобы сортировать предметы в...
128 просмотров
schedule
15.07.2023
Ветка и переплет ранца Python
Я потратил неделю, работая над этой веткой и связанным кодом для задачи о рюкзаке, и я просмотрел множество статей и книг по этой теме. Однако когда я запускаю свой код, я не получаю ожидаемого результата. Входные данные принимаются из текстового...
12837 просмотров
schedule
06.11.2022
Рекурсивный против итеративного, чтобы получить больше производительности
С точки зрения производительности, какой подход лучше подходит для задачи о рюкзаке: итеративный или рекурсивный?
Ограничено 1 sec Мне нужно разобраться, какими из 40 предметов следует заполнить рюкзак, чтобы получить самые ценные предметы,...
218 просмотров
schedule
12.06.2023
решение ранцевого динамического программирования отладки
Я попытался решить классическую проблему с кнапсапом самостоятельно. Но я получаю неправильный ответ как 108 . Не могли бы вы помочь мне понять, что я сделал не так. Здесь я использую recursion .
Ограничение по весу 10
ответ 5+3+2 ==>...
108 просмотров
schedule
09.05.2022
Подходит ли здесь алгоритм рюкзака 0/1?
У меня есть три категории ввода, каждая из которых имеет диапазон воздействия.
Категория 1: 20–16
Категория 2: 15–5
Кат 3 : 4 -1
У меня есть файл, скажем, с N случайно сгенерированными категориями. Я пытаюсь получить сумму влияния для...
85 просмотров
schedule
09.10.2022
Как я могу обойти ValueError из random.sample в Python?
Я пытаюсь написать код для задачи о рюкзаке. Где есть рюкзак с грузоподъемностью, и вы выбираете определенную комбинацию предметов, чтобы найти наилучшее возможное решение. Однако я пытаюсь случайным образом сгенерировать возможные решения. Таким...
41 просмотров
schedule
29.07.2023
как найти лучший элемент в сумке в рюкзаке
как я могу найти лучшие предметы в сумке в задаче KNAPSACK в рекурсивном режиме с C #?
Я пытался собрать индексы, функция которых возвращает для них большее значение, но, похоже, у меня не получилось....
static int recursiveknapsnack(int i,int...
264 просмотров
schedule
16.08.2022
рюкзак с требованием выбрать по одному предмету из множества наборов
У меня есть понимание основной проблемы с рюкзаком 0-1 и ее решения. Я пытаюсь решить вариант проблемы 0-1, когда вместо того, чтобы выбирать любую комбинацию элементов из одного списка, вы должны выбрать ровно один элемент из множества наборов...
1478 просмотров
schedule
19.03.2023
Вариант рюкзака в JavaScript
Я попытался реализовать этот алгоритм решения проблемы с рюкзаком в JavaScript, но решения s_opt, которые я получаю, имеют больший общий вес чем L_max.
Что я делаю не так?
Я подозреваю, что это может быть связано с замыканиями в рекурсии ....
907 просмотров
schedule
17.09.2022
Как распределить количество элементов в ведре так, чтобы оно было в пределах диапазона — алгоритм
Я решал проблему, где, скажем, у меня есть 50 элементов n1, n2, n3, ... , n50 .
Теперь у меня есть ограниченное количество ведер, скажем, 5 ведер, и ведро может содержать диапазон, скажем, только от 100 до 150 (что есть не что иное, как сумма...
909 просмотров
schedule
19.09.2022
