Рюкзак 0/1 - Несколько пояснений по псевдокоду Wiki
Вот код в статье en.wikipedia о проблеме ранца:
// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
for w from 0 to W do
m[0, w] := 0
end for
for i from 1 to n do
for j from 0 to W do
if j >= w[i] then
m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])
else
m[i, j] := m[i-1, j]
end if
end for
end for
У меня есть два момента, которые мой усталый мозг не может решить. Они незначительные, я уверен, но я действительно мог бы использовать помощь.
• Каков размер массива m[]? м [п, Вт]? Если это так, псевдокод игнорирует последнюю строку и последний столбец, потому что он заполняет всю первую строку нулями (цикл for() с m[0,w]:= 0), а затем циклически переходит от 1 до n, и от 0 до W. Например, для 3 различных предметов (n==3) и вместимостью 4 (W==3), это m[3,4] или m [4,5]?
• Где-нибудь есть примеры динамического алгоритма ранца?
2 ответа
Размер массива составляет (n + 1) × (W + 1), поскольку значения варьируются от [0, 0] до [n, W] включительно.
Интерпретация сетки следующая: позиция [k, w] представляет собой максимальное значение, которое вы можете получить, используя первые k элементов (при условии, что элементы пронумерованы 1, 2, ..., n) и не содержат больше чем общий вес
Причина, по которой первая строка полностью установлена в 0, заключается в том, что любая запись в форме [0, w] соответствует максимальному значению, которое вы можете получить, используя первые 0 элементов и имея не более w веса. Это всегда ноль, так как вы никогда не сможете получить никакого значения, не выбирая никаких предметов. Это соответствует базовому случаю рекурсии.
Строки после первой заполняются с использованием следующей идеи: если вы хотите попробовать выбрать k-й предмет, вам сначала нужно убедиться, что у вас есть возможность его удерживать (это означает, что w должно быть не менее w[k]). Если вы не можете удержать его, ваш лучший вариант - максимально использовать первые k - 1 предметов с учетом вашего текущего ограничения веса (поэтому вам лучше всего взять значение, соответствующее m[k - 1, w] Если вы можете удерживать предмет, вы можете либо не брать его (и, как и прежде, максимально использовать другие предметы, приносящие m[k - 1, w]), либо взять его и максимизировать оставшиеся грузоподъемность с остальными предметами. Это дает вам значение v[k] + m[k - 1, w - w[k]].
Надеюсь это поможет!
Я знаю, что на него уже ответили, просто добавив версии кода в C#, просто для справки (для упрощенного ранца вы можете обратиться к: Как мне рекурсивно решить "классический" алгоритм ранца?):
версия 1. Решение с использованием динамического программирования (аналогично вики) - снизу вверх (табличный подход)
Версия 2. Решение с использованием динамического программирования, но сверху вниз (Memoization - ленивый)
версия 3. Рекурсивная (просто рекурсивное решение без использования перекрывающихся подзадач или оптимальных свойств подструктуры, позволяющих использовать DP)
Версия 4. Грубая сила (прохождение всех комбинаций)
Ссылки: http://en.wikipedia.org/wiki/Knapsack_problem, Как мне рекурсивно решить "классический" алгоритм ранцев?
Табличный - DP - Версия (O (nW) - псевдополином) - O (n W) память - снизу вверх
public int Knapsack_0_1_DP_Tabular_Bottom_Up(int[] weights, int[] values, int maxWeight)
{
this.ValidataInput_Knapsack_0_1(weights, values, maxWeight);
int[][] DP_Memoization_Max_Value_Cache = new int[values.Length + 1][];
for (int i = 0; i <= values.Length; i++)
{
DP_Memoization_Max_Value_Cache[i] = new int[maxWeight + 1];
for (int j = 0; j <= maxWeight; j++)
{
DP_Memoization_Max_Value_Cache[i][j] = 0; //yes, its default -
}
}
/// f(i, w) = f(i-1, w) if Wi > w
/// Or, max (f(i-1, w), f(i-1, w-Wi) + Vi
/// Or 0 if i < 0
for(int i = 1; i<=values.Length; i++)
{
for(int w = 1; w <= maxWeight; w++)
{
//below code can be refined - intentional as i just want it
//look similar to other 2 versions (top_to_bottom_momoization
//and recursive_without_resuing_subproblem_solution
int maxValueWithoutIncludingCurrentItem =
DP_Memoization_Max_Value_Cache[i - 1][w];
if (weights[i - 1] > w)
{
DP_Memoization_Max_Value_Cache[i][w] = maxValueWithoutIncludingCurrentItem;
}
else
{
int maxValueByIncludingCurrentItem =
DP_Memoization_Max_Value_Cache[i - 1][w - weights[i - 1]]
+ values[i-1];
int overAllMax = maxValueWithoutIncludingCurrentItem;
if(maxValueByIncludingCurrentItem > overAllMax)
{
overAllMax = maxValueByIncludingCurrentItem;
}
DP_Memoization_Max_Value_Cache[i][w] = overAllMax;
}
}
}
return DP_Memoization_Max_Value_Cache[values.Length][maxWeight];
}
DP - Мемоизация - Сверху вниз - Ленивая оценка
/// <summary>
/// f(i, w) = f(i-1, w) if Wi > w
/// Or, max (f(i-1, w), f(i-1, w-Wi) + Vi
/// Or 0 if i < 0
/// </summary>
int Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy_Recursive(int[] weights, int[] values,
int index, int weight, int?[][] DP_Memoization_Max_Value_Cache)
{
if (index < 0)
{
return 0;
}
Debug.Assert(weight >= 0);
#if DEBUG
if ((index == 0) || (weight == 0))
{
Debug.Assert(DP_Memoization_Max_Value_Cache[index][weight] == 0);
}
#endif
//value is cached, so return
if(DP_Memoization_Max_Value_Cache[index][weight] != null)
{
return DP_Memoization_Max_Value_Cache[index][weight].Value;
}
Debug.Assert(index > 0);
Debug.Assert(weight > 0);
int maxValueWithoutIncludingCurrentItem = this.Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy_Recursive
(weights, values, index - 1, weight, DP_Memoization_Max_Value_Cache);
if (weights[index-1] > weight)
{
DP_Memoization_Max_Value_Cache[index][weight] = maxValueWithoutIncludingCurrentItem;
//current item weight is more, so we cant include - so, just return
return maxValueWithoutIncludingCurrentItem;
}
int overallMaxValue = maxValueWithoutIncludingCurrentItem;
int maxValueIncludingCurrentItem = this.Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy_Recursive
(weights, values, index - 1, weight - weights[index-1],
DP_Memoization_Max_Value_Cache) + values[index - 1];
if(maxValueIncludingCurrentItem > overallMaxValue)
{
overallMaxValue = maxValueIncludingCurrentItem;
}
DP_Memoization_Max_Value_Cache[index][weight] = overallMaxValue;
return overallMaxValue;
}
И публичный метод для вызова (для получения подробной информации о вызывающих, см. Ниже тесты модулей)
public int Knapsack_0_1_DP_Tabular_Bottom_Up(int[] weights, int[] values, int maxWeight)
{
this.ValidataInput_Knapsack_0_1(weights, values, maxWeight);
int[][] DP_Memoization_Max_Value_Cache = new int[values.Length + 1][];
for (int i = 0; i <= values.Length; i++)
{
DP_Memoization_Max_Value_Cache[i] = new int[maxWeight + 1];
for (int j = 0; j <= maxWeight; j++)
{
DP_Memoization_Max_Value_Cache[i][j] = 0; //yes, its default -
}
}
/// f(i, w) = f(i-1, w) if Wi > w
/// Or, max (f(i-1, w), f(i-1, w-Wi) + Vi
/// Or 0 if i < 0
for(int i = 1; i<=values.Length; i++)
{
for(int w = 1; w <= maxWeight; w++)
{
//below code can be refined - intentional as i just want it
//look similar to other 2 versions (top_to_bottom_momoization
//and recursive_without_resuing_subproblem_solution
int maxValueWithoutIncludingCurrentItem =
DP_Memoization_Max_Value_Cache[i - 1][w];
if (weights[i - 1] > w)
{
DP_Memoization_Max_Value_Cache[i][w] = maxValueWithoutIncludingCurrentItem;
}
else
{
int maxValueByIncludingCurrentItem =
DP_Memoization_Max_Value_Cache[i - 1][w - weights[i - 1]]
+ values[i-1];
int overAllMax = maxValueWithoutIncludingCurrentItem;
if(maxValueByIncludingCurrentItem > overAllMax)
{
overAllMax = maxValueByIncludingCurrentItem;
}
DP_Memoization_Max_Value_Cache[i][w] = overAllMax;
}
}
}
return DP_Memoization_Max_Value_Cache[values.Length][maxWeight];
}
Рекурсивно - с подзадачами DP - но без повторного использования подзадач (это должно показать, как проще изменить рекурсивную версию на DP сверху вниз (версия Memoization)
public int Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure(int[] weights, int[] values, int maxWeight)
{
this.ValidataInput_Knapsack_0_1(weights, values, maxWeight);
int v = this.Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure_Recursive(weights, values, index: weights.Length-1, weight: maxWeight);
return v;
}
/// <summary>
/// f(i, w) = f(i-1, w) if Wi > w
/// Or, max (f(i-1, w), f(i-1, w-Wi) + Vi
/// Or 0 if i < 0
/// </summary>
int Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure_Recursive(int[] weights, int[] values, int index, int weight)
{
if (index < 0)
{
return 0;
}
Debug.Assert(weight >= 0);
int maxValueWithoutIncludingCurrentItem = this.Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure_Recursive(weights,
values, index - 1, weight);
if(weights[index] > weight)
{
//current item weight is more, so we cant include - so, just return
return maxValueWithoutIncludingCurrentItem;
}
int overallMaxValue = maxValueWithoutIncludingCurrentItem;
int maxValueIncludingCurrentItem = this.Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure_Recursive(weights,
values, index - 1, weight - weights[index]) + values[index];
if(maxValueIncludingCurrentItem > overallMaxValue)
{
overallMaxValue = maxValueIncludingCurrentItem;
}
return overallMaxValue;
}
Грубая сила (прохождение всех комбинаций)
private int _maxValue = int.MinValue;
private int[] _valueIndices = null;
public void Knapsack_0_1_BruteForce_2_Power_N(int[] weights, int[] values, int maxWeight)
{
this.ValidataInput_Knapsack_0_1(weights, values, maxWeight);
this._maxValue = int.MinValue;
this._valueIndices = null;
this.Knapsack_0_1_BruteForce_2_Power_N_Rcursive(weights, values, maxWeight, 0, 0, 0, new List<int>());
}
private void Knapsack_0_1_BruteForce_2_Power_N_Rcursive(int[] weights, int[] values, int maxWeight, int index, int currentWeight, int currentValue, List<int> currentValueIndices)
{
if(currentWeight > maxWeight)
{
return;
}
if(currentValue > this._maxValue)
{
this._maxValue = currentValue;
this._valueIndices = currentValueIndices.ToArray();
}
if(index == weights.Length)
{
return;
}
Debug.Assert(index < weights.Length);
var w = weights[index];
var v = values[index];
//see if the current value, conributes to max value
currentValueIndices.Add(index);
Knapsack_0_1_BruteForce_2_Power_N_Rcursive(weights, values, maxWeight, index + 1, currentWeight + w,
currentValue + v, currentValueIndices);
currentValueIndices.Remove(index);
//see if current value, does not contribute to max value
Knapsack_0_1_BruteForce_2_Power_N_Rcursive(weights, values, maxWeight, index + 1, currentWeight, currentValue,
currentValueIndices);
}
Модульные тесты 1
[TestMethod]
public void Knapsack_0_1_Tests()
{
int[] benefits = new int[] { 60, 100, 120 };
int[] weights = new int[] { 10, 20, 30 };
this.Knapsack_0_1_BruteForce_2_Power_N(weights, values: benefits, maxWeight: 50);
Assert.IsTrue(this._maxValue == 220);
int v = this.Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure(weights,
values: benefits, maxWeight: 50);
Assert.IsTrue(v == 220);
v = this.Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy(weights,
values: benefits, maxWeight: 50);
Assert.IsTrue(v == 220);
v = this.Knapsack_0_1_DP_Tabular_Bottom_Up(weights,
values: benefits, maxWeight: 50);
Assert.IsTrue(v == 220);
benefits = new int[] { 3, 4, 5, 8, 10 };
weights = new int[] { 2, 3, 4, 5, 9 };
this.Knapsack_0_1_BruteForce_2_Power_N(weights, values: benefits, maxWeight: 20);
Assert.IsTrue(this._maxValue == 26);
v = this.Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure(weights, values: benefits,
maxWeight: 20);
Assert.IsTrue(v == 26);
v = this.Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy(weights,
values: benefits, maxWeight: 20);
Assert.IsTrue(v == 26);
v = this.Knapsack_0_1_DP_Tabular_Bottom_Up(weights,
values: benefits, maxWeight: 20);
Assert.IsTrue(v == 26);
benefits = new int[] { 3, 4, 5, 6};
weights = new int[] { 2, 3, 4, 5 };
this.Knapsack_0_1_BruteForce_2_Power_N(weights, values: benefits, maxWeight: 5);
Assert.IsTrue(this._maxValue == 7);
v = this.Knapsack_0_1_OverlappedSubPromblems_OptimalSubStructure(weights, values: benefits,
maxWeight: 5);
Assert.IsTrue(v == 7);
v = this.Knapsack_0_1_DP_Memoization_Top_To_Bottom_Lazy(weights,
values: benefits, maxWeight: 5);
Assert.IsTrue(v == 7);
v = this.Knapsack_0_1_DP_Tabular_Bottom_Up(weights,
values: benefits, maxWeight: 5);
Assert.IsTrue(v == 7);
}
Модульные тесты 2
[TestMethod]
public void Knapsack_0_1_Brute_Force_Tests()
{
int[] benefits = new int[] { 60, 100, 120 };
int[] weights = new int[] { 10, 20, 30 };
this.Knapsack_0_1_BruteForce_2_Power_N(weights, values: benefits, maxWeight: 50);
Assert.IsTrue(this._maxValue == 220);
Assert.IsTrue(this._valueIndices.Contains(1));
Assert.IsTrue(this._valueIndices.Contains(2));
Assert.IsTrue(this._valueIndices.Length == 2);
this._maxValue = int.MinValue;
this._valueIndices = null;
benefits = new int[] { 3, 4, 5, 8, 10 };
weights = new int[] { 2, 3, 4, 5, 9 };
this.Knapsack_0_1_BruteForce_2_Power_N(weights, values: benefits, maxWeight: 20);
Assert.IsTrue(this._maxValue == 26);
Assert.IsTrue(this._valueIndices.Contains(0));
Assert.IsTrue(this._valueIndices.Contains(2));
Assert.IsTrue(this._valueIndices.Contains(3));
Assert.IsTrue(this._valueIndices.Contains(4));
Assert.IsTrue(this._valueIndices.Length == 4);
}