2

ナップザック問題に関する 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

疲れた頭では解決できないポイントが 2 つあります。彼らは確かにマイナーですが、私は本当に助けを使うことができました.

• m[] 配列のサイズは？m[n,W]? そうである場合、最初の行全体をゼロで埋め (m[0,w] := 0 での for() ループ)、1 から n までループするため、最後の行と最後の列を無視する疑似コードです。たとえば、3 つの異なるアイテム (n==3) と 4 つの容量 (W==3) の場合、m[3,4] または m[4,5] ですか?

•動的なナップザック アルゴリズムのより良い例はありますか?

4

2 に答える 2

4

値の範囲が [0, 0] から [n, W] までであるため、配列のサイズは (n + 1) × (W + 1) です。

グリッドの解釈は次のとおりです。位置 [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]] が得られます。

お役に立てれば！

于 2013-06-12T19:41:56.803 に答える
2

参照用にC＃でコードバージョンを追加するだけで、すでに回答されていることを知っています（単純化されたナップザックについては、「クラシック」ナップザックアルゴリズムを再帰的に解決するにはどうすればよいですか?）：

バージョン 1.動的プログラミング (wiki に類似) を使用した解決 - ボトムアップ (表形式のアプローチ)

バージョン 2.動的プログラミングを使用して解決するが、上から下へ (メモ化 - 怠惰)

バージョン 3.再帰的 (重複部分問題または DP を使用できる最適な部分構造プロパティを使用しない再帰的ソリューションのみ)

バージョン 4.ブルート フォース (すべての組み合わせを通過)

参考文献: http://en.wikipedia.org/wiki/Knapsack_problem、「古典的な」ナップザック アルゴリズムを再帰的に解決するにはどうすればよいですか?

表形式 - DP - バージョン (O(n W) - 疑似多項式) - 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 メソッド (呼び出し元の詳細については、以下のユニット テストを参照してください)

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);
        }
于 2014-07-23T09:05:31.250 に答える