在0/1背包问题（递归蛮力）中打印结果

Question

public static int KnapSack(int capacity, Item[] items, int numItems) {
    if (numItems == 0 || capacity == 0)
        return 0;
    if (items[numItems-1].weight > capacity)
        return KnapSack(capacity, items, numItems-1);
    else {
        int took = items[numItems-1].value + KnapSack(capacity - items[numItems-1].weight, items, numItems-1);
        int left = KnapSack(capacity, items, numItems-1);
        return Math.max(took, left);
    }     
}  

我已经为背包问题编写了一个有效的0/1递归暴力算法。现在我想知道如何输出可行解（即从物品集合中收集到的物品）。我尝试了很多方法，例如添加到列表并尝试跟踪添加了什么物品，但由于实现或设计问题，这些方法都没有成功。所以我来这里寻求帮助，谢谢！

- Kevin Le

Answer 1

为了跟踪所取的物品，可以尝试以下方法：

public static int KnapSack(int capacity, Item[] items, int numItems, ArrayList<Integer> taken) {
    if (numItems == 0 || capacity == 0)
        return 0;
    if (items[numItems-1].weight > capacity)
        return KnapSack(capacity, items, numItems-1, taken);
    else {
        final int preTookSize = taken.size();
        final int took = items[numItems-1].value + KnapSack(capacity - items[numItems-1].weight, items, numItems-1, taken);

        final int preLeftSize = taken.size();
        final int left = KnapSack(capacity, items, numItems-1, taken);

        if (took > left) {
            if (taken.size() > preLeftSize)
                taken.removeRange(preLeftSize, taken.size());
            taken.add(Integer.valueOf(numItems - 1));
            return took;
        }
        else {
            if (preLeftSize > preTookSize)
                taken.removeRange(preTookSize, preLeftSize);
            return left;
        }
    }     
}

这可能不是最有效的方法，但我认为它应该可以工作。

（为了提高效率，您可以尝试预先分配足够大的已占用ArrayList，以使在递归循环过程中不需要进行任何分配。）

- Turix

---

这个完美地运作了。感谢你的帮助，但愿我有足够的声望来点赞你！ - Kevin Le

Answer 2

我知道这个问题已经有答案了，只是提供C#代码版本作为参考（对于简化的背包问题，您可以参考：如何递归解决“经典”背包算法？）： 版本1. 使用动态规划求解（类似于维基百科） - 自下而上（表格法）。 版本2. 使用动态规划但自上而下（记忆化-惰性求值）。 版本3. 递归（仅使用递归解决，不使用重叠子问题或最优子结构属性，这些属性使得可以使用DP）。 版本4. 暴力枚举（遍历所有组合）-在字段(this._valueIndices, this._maxValue)中捕获最大值和值索引（请参见tests2 - 应显示这些捕获值的调用者和用法）。

参考资料：http://en.wikipedia.org/wiki/Knapsack_problem，如何递归解决“经典”背包算法？ 表格DP版本（O(nW) - 伪多项式）- O（nW）内存 - 自下而上

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自顶向下（记忆化版本）

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);
        }

- Dreamer