こんにちは。ふぁんたです。





サイゼリヤ1000円ガチャなるものが流行りました。

https://qiita.com/marusho_summers/items/a2d3681fac863734ec8a

1000円以内の組み合わせを選んでカロリー表示してくれるアプリケーションです。







で、そのカロリー最大化問題を、量子コンピュータで行った記事が書かれました。

https://qiita.com/hodaka0714/items/cf44b4ece992a39b5be4

確率的に解く技法らしいので、記事の最後に、





「厳密にナップザック問題を解こうとお考えの方は動的計画法などのアルゴリズムを参考に計算することをおすすめします。」





とありました。







自分も何度も躓いた動的計画法、確認の意味も込めて組んでみましょう。

動的計画法の根底となる考え方

例として、300円のメニューと、400円のメニューがあるとします。

「400円で最大カロリーの組み合わせ」　は、300円のメニューか、400円のメニューです。

「500円で最大カロリーの組み合わせ」も同じです。

「600円で最大カロリーの組み合わせ」は、300円のメニュー２つか、400円のメニュー１つのどっちかです。



数字が小さいとわかりやすいのですが、ここでいきなり

「10000円で最大カロリーの組み合わせ」を聞かれてもわかりません。



ここで、ちょっと考えて、「〇〇円で最大カロリーの組み合わせ」という言葉を式の中に使ってしまうと、

「10000円で最大カロリーの組み合わせ」は

「9700円で最大カロリーの組み合わせ」に300円のメニューを足したもの　と

「9600円で最大カロリーの組み合わせ」に400円のメニューを足したもの　の

どっちか大きい方

と定義することが出来ます。

これを、金額が小さい方から計算していくのが動的計画法の基本的な考え方になります。

1000円で最強カロリーの組み合わせ

求めてみました。何カロリーになるかを計算しながら、組み合わせも知りたかったので、無理やりクラスをねじ込んだ動的計画法にしました。

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

public class SAIZE

{

    public static void Main()

    {

        int N = 115;

        saizeriya[] array = new saizeriya[N];

        saizeriya max_cospa = new saizeriya(0, "", 100, 1);

        for (int i = 0; i < N; i++)

        {

            var split = Console.ReadLine().Split();

            array[i] = new saizeriya(int.Parse(split[0]), split[1], int.Parse(split[4]), int.Parse(split[5]));

            if (array[i].cal / array[i].cost > max_cospa.cal / max_cospa.cost) max_cospa = array[i];

        }

        receipt[][] dp = new receipt[N+1][];

        for (int i = 0; i < N+1; i++)

        {

            dp[i] = new receipt[1001];

            for (int j = 0; j <= 1000; j++)

            {

                dp[i][j] = new receipt();

            }

        }



        for (int i = 1; i < N+1; i++)

        {

            

            for (int j = 0;j<=1000; j++)

            {

                var candidate = dp[i-1][j];

                for (int k = 0; true; k++)

                {



                    if (j - k * array[i - 1].cost >= 0)

                    {

                       



                        candidate = (candidate.cal >= dp[i - 1][j - k * array[i - 1].cost].cal + k * array[i - 1].cal) ? candidate : new receipt(j, dp[i - 1][j - k * array[i - 1].cost].name + "," + k + "*" + array[i-1].name, dp[i - 1][j - k * array[i - 1].cost].cal + k * array[i - 1].cal);





                        dp[i][j] = candidate;

                    }

                    else

                    {

                        break;

                    }



                }

            }

        }





        for (int i = 0; i < N + 1; i++)

        {

            Console.WriteLine(i + "," + dp[i][1000]);





        }



    }

}

public class receipt

{

    public int cost;

    public string name;

    public int cal;

    public receipt()

    {

        this.cost = 0;

        this.name = "";

        this.cal = 0;

    }

    public receipt(int cost, string name, int cal)

    {

        this.cost = cost;

        this.name = name;

        this.cal = cal;

    }



}





public class saizeriya

{

    public int num;

    public string name;

    public int cost;

    public int cal;



    public saizeriya()

    {

    }

    public saizeriya(int num, string name, int cost, int cal)

    {

        this.num = num;

        this.name = name;

        this.cost = cost;

        this.cal = cal;



    }



}

public class saizeria

{

    private string Caution = "は？";

}

出た結果がこちらです。



Calorie:2030

Name:1*フォッカチオ,4*ラージライス





米！米！米！米！

金余ったからパン！



おあいそ！