【C#】ナップサック問題の最適値を満たす商品の番号を求める（動的計画法）

最近、蟻本と呼ばれる本を使って競技プログラミングの勉強をしています。 動的計画法でナップサック問題を解く部分で、最適値ではなく最適解(選ぶ品物の番号)を求めるコードが書かれていなかったので、少し調べてみました。 各品物が使われるかどうかを、作成したDPテーブルを逆順に辿って調べる必要があるらしく、意外なことにその部分に関してあまりコードが転がってなかったので、少し自分で考えてみました。

    public static class KnapsackSolver
    {
        static int[] weights = new int[] { 2, 2, 4, 3, 2};
        static int[] values = new int[] { 1, 2, 4, 2, 3};

        static int numOfItems = weights.Length;
        static int weightLimit = 4;

        //DP_tabel[i,w]はi+1番目からn番目の荷物のみを使って、残り容量wのナップサックに詰め込める価値の最大値
        static int[,] DP_tabel = new int[weights.Length + 1, weightLimit + 1];

        public static void Main()
        {
            Solve();
            var answer = GetOptimalItems();
            PrintAnswer(answer);
        }

        public static void Solve()
        {
            for (int i = numOfItems - 1; i >= 0; i--)
            {
                for (int j = 0; j <= weightLimit; j++)
                {
                    if (j < weights[i])
                    {
                        DP_tabel[i, j] = DP_tabel[i + 1, j];
                    }
                    else
                    {
                        var value1 = DP_tabel[i + 1, j];
                        var value2 = DP_tabel[i + 1, j - weights[i]] + values[i];
                        DP_tabel[i, j] = Math.Max(value1, value2);
                    }
                }
            }
        }
        
        static int[] GetOptimalItems()
        {
            var answer = new int[numOfItems];
            var enableWeight = weightLimit;

            for (int i = 0; i < numOfItems; i++)
            {
                if (enableWeight >= weights[i])
                {
                    //入れる場合に可能な最大価値
                    var value1 = DP_tabel[i + 1, enableWeight - weights[i]] + values[i];
                    //入れない場合に可能な最大価値
                    var value2 = DP_tabel[i + 1, enableWeight];

                    if (Math.Max(value1, value2) == value1)
                    {
                        answer[i] = 1;
                        enableWeight -= weights[i];
                    }
                    else
                    {
                        answer[i] = 0;
                    }
                }
            }
            return answer;
        }

        static void PrintAnswer(int[] answer)
        {
            for (int i = 0; i < answer.Length; i++)
            {
                if (answer[i] == 1) Console.WriteLine($"品物{i + 1}、重さ{weights[i]}、価値{values[i]}");
            }
        }
    }

注意しなければいけない点として、結果を逆算するときのDPテーブルの走査順は作成時と逆になります。 今回の場合は蟻本に乗ってるのと同様に i = numOfItems - 1から降順にDPテーブルを作成していますが、i = 0から昇順にDPテーブルを作成した場合は、最適解を求める際にi = numOfItems - 1からforループを始める必要があるということです。

参考：https://mathwords.net/napusaku#i-4