Эта серия представляет собой краткое изложение структур данных и алгоритмов, когда я искал работу много лет назад. Здесь есть базовые части и классические вопросы для интервью от крупных компаний. Впервые опубликовано на CSDN. Теперь он организован в серию для справки друзей, которые в нем нуждаются.Если есть какие-либо ошибки, пожалуйста, поправьте меня. Полный кодовый адрес этой серии находится по адресуздесь.
0 Обзор
Задачи о рюкзаке включают несколько вариантов 0-1 задача о рюкзаке, задача о рюкзаке полностью, задача о рюкзаке частично. Среди них самая простая часть задачи о рюкзаке, жадный алгоритм, который можно использовать для решения, в то время как динамическое программирование часто требует решения нескольких других задач о рюкзаке. Эта статья исходит из "проблема ранца девять скажем," я выбрал относительно простой 0-1 проблема рюкзака проблема рюкзака и полностью резюмировать. При этом дает код реализации, если не прав, поправьте меня, креветки. Код статьиздесь.
Задача о рюкзаке, часть 1.
Часть описания задачи о рюкзаке:Есть N элементов и емкость C рюкзака. По весу I-Thtes, которые w [i], значение равно v [i]. Решение элементов в рюкзак, который позволяет максимальному значению суммы. Обратите внимание, что это не требует, все предметы нагрузки могут быть загружены только часть статьи.
решение:Некоторые задачи о рюкзаках часто решаются с помощью жадного алгоритма, сначала вычисляющего стоимость единицы веса каждого предмета.v[i]/w[i], затем начните с предмета с наибольшей ценностью единицы, затем со второго по величине предмета, пока рюкзак не заполнится. В соответствии с этой жадной стратегией общее значение должно быть наибольшим, что относительно просто, а код реализации опускается.
2 0-1 Проблема с рюкзаком
0-1 Рюкзак Описание проблемы
Есть N предметов и рюкзак вместимостью C. Вес i-го предмета равен w[i], а значение равно v[i]. Найдите, какие предметы положить в рюкзак, максимизируйте сумму значений. Обратите внимание, что предметы можно только брать или не брать, что и означает 0-1. Частичную задачу о рюкзаке можно рассматривать как взятие золотого песка, в то время как задачу о рюкзаке 0-1 можно рассматривать как взятие золотых самородков, один из которых разделим, а другой неделим.
анализировать
Это самая основная проблема рюкзака.Характеристика такова: есть только один предмет каждого вида, и вы можете выбрать, класть его или нет. Определите состояния с подзадачами: т.е.f[i][w]Представляет максимальное значение, которое можно получить, поместив первые i предметов в рюкзак вместимостью c. Тогда его уравнение перехода состояния:
f[i][c] = max{f[i-1][c], f[i-1][c-w[i]]+v[i]}
Это уравнение очень важно, и в основном все уравнения для задач, связанных с рюкзаком, выводятся из него. Поэтому необходимо объяснить это подробно:将前 i 件物品放入容量为 c 的背包中Эта подзадача может быть преобразована в задачу, включающую только первые i-1 элементы, если рассматривается только стратегия i-го элемента (ставить или нет).
- Если вы удерживаете элементы I, то проблема трансформируется в
前 i-1 件物品放入容量为 v 的背包中, значениеf[i-1][c]; - Если поставить i-й пункт, то проблема превращается в
前 i-1 件物品放入剩下的容量为 c-w[i] 的背包中, максимальное значение, которое может быть получено в это время, равноf[i-1][c-w[i]]Плюс значение v[i], полученное при добавлении i-го элемента.
Оптимизация сложности пространства
Временная и пространственная сложность вышеуказанных методовO(CN), временная сложность больше не должна оптимизироваться, но пространственная сложность может быть оптимизирована дляO(N). из-за расчетаf[i][c], нам нужно использовать толькоf[i-1][c]иf[i-1][c-w[i]], поэтому можно сохранить их значения через одномерный массив.Трюк, используемый здесь, заключается в том, чтобы начать сc=C...0Начните отталкивать, чтобы убедиться, что вы ищетеf[c]когдаf[c-w[i]]сохраненоf[i-1][c-w[i]]значение . Обратите внимание, что невозможноc=0...Cпродвигайтесь вперед вот так, потому что это вызоветf[c-w[i]]Значениеf[i][c-w[i]]вместоf[i-1][c-w[i]. Нижняя граница здесь может быть оптимизирована фактически только изc=C...w[i]Чтобы не было лишних расчетов. Псевдокод выглядит следующим образом:
for i=0..N-1
for c=C..w[i]
f[c]=max{f[c],f[c-w[i]]+v[i]};
Окончательный код реализации выглядит следующим образом:
int knap01(int N, int C, int w[], int v[])
{
int *f = (int *)calloc(sizeof(int), C+1);
int i, c;
for (i = 0; i < N; i++) {
for (c = C; c >= w[i]; c--) {
f[c] = max(f[c], f[c-w[i]] + v[i]);
}
printf("%d: ", i+1);
printIntArray(f, C+1); // 打印f数组
}
return f[C];
}
Результаты теста следующие, то есть при вместимости рюкзака 10 загружены 1-й и 2-й предметы (индекс начинается с 0), общий вес 4+5=9, а максимальное значение 5+6= 11.
参数：
w = [3, 4, 5] //物品重量列表
v = [4, 5, 6] //物品价值列表
C = 10
结果（打印数组f，i为选择的物品索引，c为背包重量，值为背包物品价值）：
i/c 0 1 2 3 4 5 6 7 8 9 10
0: 0 0 0 4 4 4 4 4 4 4 4
1: 0 0 0 4 5 5 5 9 9 9 9
2: 0 0 0 4 5 6 6 9 10 11 11
KNap01 max: 11
Начальные данные
В задаче о рюкзаке, которую мы видели, чтобы найти оптимальное решение, на самом деле есть два разных способа задать вопрос. Некоторые задачи требуют оптимального решения, когда «рюкзак просто полон», а некоторые задачи не требуют, чтобы рюкзак был полным. Один из способов различить эти два метода — время инициализации.
Если это первый вопрос, то требуется ровно заполнить рюкзак, тогда при инициализации, кроме f[0] будет 0f[1..C]настроены на-∞, что гарантирует, что конечное f[N] является оптимальным решением, которое как раз заполняет рюкзак. Если нет требования, чтобы рюкзак был полным, а только ожидается, что цена будет как можно больше, инициализация должна бытьf[0..C]Все установлено на 0.
Зачем? Это можно понять так: инициализированный массив f на самом деле является допустимым состоянием, когда в рюкзак нечего положить. Если требуется, чтобы рюкзак был точно полон, то только рюкзак с вместимостью 0 может быть «точно заполнен» чем-то со значением 0, а рюкзаки с другими вместимостью не имеют законного решения и принадлежат неопределенному состоянию, и их значения все должны быть -∞. Если рюкзак не обязательно должен быть полным, то рюкзак любой вместимости имеет допустимое решение «ничего», и значение этого решения равно 0, поэтому все начальные значения состояния равны 0.
3 Завершить задачу о рюкзаке
описание проблемы
Есть N предметов и рюкзак вместимости C, причем доступно бесконечное количество штук каждого предмета. Вес i-го предмета равен w[i], а значение равно v[i]. Выясните, какие предметы загружаются в рюкзак, чтобы общий вес этих предметов не превышал вместимости рюкзака, а общая стоимость была наибольшей, и предметы не могли быть загружены только частично.
Основная мысль
Эта проблема очень похожа на проблему 0-1 Knaxackack, разница состоит в том, что каждый элемент имеет бесконечные части. Что именно с точки зрения каждого предмета рассмотрения, связанные с его политикой, было не принимать или не принимать два типа, но приходится брать 0, взять один, взять два ... И так много. Если вы все еще думаете, когда решение в соответствии с рюкзаком 01, поэтому f [i] [c] представляет собой такие виды товаров, прежде чем я просто поставил максимальную емкость рюкзака C. Я все еще могу написать уравнение состояния в соответствии с различными стратегиями для каждого элемента, как это:
f[i][c] = max{f[i-1][c-k*w[i]]+ k*w[i]| 0<=k*w[i]<=c }
Это то же самое, что и задача о рюкзаке 0-1, нужно решить O(CN) состояний, но время решения каждого состояния больше не является постоянным.f[i][c]время - этоO(c/w[i]), полную сложность можно рассматривать какO(CN*Σ(c/w[i])), относительно большой. Код реализации выглядит следующим образом:
/*
* 完全背包问题
*/
int knapComplete(int N, int C, int w[], int v[])
{
int *f = (int *)calloc(sizeof(int), C+1);
int i, c, k;
for (i = 0; i < N; i++) {
for (c = C; c >= 0; c--) {
for (k = 0; k <= c/w[i]; k++) {
f[c] = max(f[c], f[c-k*w[i]] + k*v[i]);
}
}
printf("%d: ", i+1);
printIntArray(f, C+1);
}
return f[C];
}
Используя тот же пример, что и задача о рюкзаке 0-1, результат выполнения программы следующий: максимальное значение равно 13, то есть выбрано 2 предмета веса 3 и 1 предмет веса 4, а общее значение равно высший, который4*2 + 5 = 13.
i/c: 0 1 2 3 4 5 6 7 8 9 10
0: 0 0 0 4 4 4 8 8 8 12 12
1: 0 0 0 4 5 5 8 9 10 12 13
2: 0 0 0 4 5 6 8 9 10 12 13
KNapComplete max: 13
Преобразование в задачу о рюкзаке 0-1
Поскольку задача о рюкзаке 01 является самой простой задачей о рюкзаке, то мы можем рассматривать полную задачу о рюкзаке 01 как задачу о рюкзаке, которую необходимо решить. Простейшая идея состоит в том, что, учитывая i-е количество выбранных элементовC/w[i]предметов, поэтому i-й предмет можно преобразовать вC/w[i]предмет постоянной стоимости и стоимости, а затем решить задачу о рюкзаке 01. Это совсем не улучшает временную сложность основной идеи, но, в конце концов, дает нам идею преобразования полной задачи о рюкзаке в задачу о рюкзаке 01: разбиение одного предмета на несколько предметов.
Более эффективный метод преобразования: разбить i-й предмет на весw[i]*2^k, значениеw[i]*2^kряд элементов, где k удовлетворяетw[i]*2^k<=C. Это бинарная идея, поскольку сколько бы элементов i-го предмета ни было выбрано оптимальной стратегией, их всегда можно выразить в виде нескольких2^kсумма предметов. Разбейте каждый элемент наO(log C/w[i])Часть элемента является большим улучшением. Но у нас лучшеO(CN)алгоритм.
Дальнейшая оптимизация — решение O(CN)
Мы можем пройти в обратном порядке задачи о рюкзаке 0-1, так что мы можем получить решение O (CN) Псевдокод выглядит следующим образом:
for i=0..N-1
for c=w[i]..C
f[c]=max{f[c],f[c-w[i]]+v[i]};
Этот псевдокод отличается от псевдокода рюкзака 0-1 только порядком циклов C. Причина, по которой должен следовать рюкзак 0-1v=V..0цикл в обратном порядке. Это потому, что состояние в i-м цикле гарантированоf[i][c]по состояниюf[i-1][c-w[i]]рекурсивно. Другими словами, это как раз для того, чтобы каждый элемент выбирался только один раз, для того, чтобы при рассмотрении стратегии «выбрать i-й элемент» она основывалась на подрезультате, который никогда не выбирался для i-го элемента.f[i-1][c-w[i]]. А теперь особенность полного рюкзака в том, что каждый предмет можно выбирать бесконечно, поэтому при рассмотрении стратегии «добавление предмета i» нам нужен подрезультат, который мог быть выбран в предмете i.f[i][c-w[i]], поэтому можно и нужно использоватьc=w[i]..Cцикл последовательности. Вот почему эта простая программа работает. Код реализации выглядит следующим образом:
/**
* 完全背包问题-仿01背包解法
*/
int knapCompleteLike01(int N, int C, int w[], int v[])
{
int *f = (int *)calloc(sizeof(int), C+1);
int i, c;
for (i = 0; i < N; i++) {
for (c = w[i]; c <= C; c++) {
f[c] = max(f[c], f[c-w[i]] + v[i]);
}
printf("%d: ", i+1);
printIntArray(f, C+1);
}
return f[C];
}