プログラミングコンテストチャレンジブック p52 ナップサック問題(C#)

問題

重さと価値がそれぞれ、wi,viであるようなn個の品物があります。これらの品物から、重さの総和がWを超えないように選んだときの、価値の総和の最大値を求めなさい。

全探索で解いた

自分(正解)

public class Program
{
    public static void Main()
    {
        int n = 4;
        int W = 5;
        int[,] list = new int[,] { { 2, 3 }, { 1, 2 }, { 3, 4 }, { 2, 2 } };
        int ans;

        ans = exec(0, W);
        Console.WriteLine("答えは、{0}", ans);

        int exec(int index, int weight)//index番目以降を使って、残り入る重さはWだけある
        {
            if (index == n) return 0;
            if (weight - list[index, 0] < 0)
            {
                return exec(index + 1, weight);
            }
            else
            {
                return Math.Max(exec(index + 1, weight - list[index, 0]) + list[index, 1], exec(index + 1, weight));
            }
        }
    }
}