プログラミングコンテストチャレンジブック p58 個数制限なしナップサック問題(C#)

問題

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

全探索

自分(正解)

using System;

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

        //個数制限なしの解答
        //indexをMax(入れてそのまま, 入れずに次へ)にする
        //同じ品物を入れ続けた際の終了(次のindexに行く)条件は、weight - list[index,0]が0を下回ること。次の品物なら入る可能性があるが、少なくとも同じ品物ではこれ以上入れることができないので。



        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, weight - list[index, 0]) + list[index, 1], exec(index + 1, weight));
            }
        }
    }
}