「サイゼリヤで1000円あれば最大何kcal摂れるのか」をTeX言語で計算する ～TeX言語で動的計画法(DP)～ https://doratex.hatenablog.jp/entry/20190520/1558323856

saizeriyaKnapsackDP.pdf

saizeriyaKnapsackDP.tex

%#!(u)platex
\documentclass[dvipdfmx,autodetect-engine]{jsarticle}
\usepackage{pgffor}
\usepackage{tcolorbox}
\tcbuselibrary{skins,breakable}

\tcbset{enhanced jigsaw,colback=red!5!white,colframe=red!75!black,breakable,fonttitle=\gtfamily,before upper=\setlength\parindent{1zw}}

\makeatletter

\newcount\Knapsack@numberOfExecutions
\newcounter{Knapsack@numberOfItems}

\def\Knapsack@calorie{@calorie@}
\def\Knapsack@title{@title@}
\def\Knapsack@price{@price@}
\def\Knapsack@restrictedCalorie{@restrictedCalorie@}
\def\Knapsack@restrictedTitles{@restrictedTitles@}
\def\Knapsack@restrictedPrice{@restrictedPrice@}

%%% 以下項目の「i番目」は0始まり

%%% 項目の「タイトルi,カロリーi,値段i」を分解してそれぞれ \@namedef
\def\Knapsack@splitItems#1,#2,#3\relax{%
  \global\@namedef{\Knapsack@prefix\Knapsack@title\arabic{Knapsack@numberOfItems}}{#1}%
  \global\@namedef{\Knapsack@prefix\Knapsack@calorie\arabic{Knapsack@numberOfItems}}{#2}%
  \global\@namedef{\Knapsack@prefix\Knapsack@price\arabic{Knapsack@numberOfItems}}{#3}%
  \stepcounter{Knapsack@numberOfItems}%
}

\newcount\Knapsack@c
\newcount\Knapsack@p
\newcount\Knapsack@A
\newcount\Knapsack@B

%%% 「項目はi番目未満，値段上限値j」の下でのカロリーの総和の最大値を取得
\def\Knapsack@getRestrictedCalorie#1#2{%
  \@ifundefined{\Knapsack@prefix\Knapsack@restrictedCalorie\the\numexpr#1\relax @\the\numexpr#2\relax}{0}{\@nameuse{\Knapsack@prefix \Knapsack@restrictedCalorie\the\numexpr#1\relax @\the\numexpr#2\relax}}%
}

%%% 「項目はi番目未満，値段上限値j」の下でカロリーの総和を最大化する項目の選び方のタイトルをコンマ区切りで列挙した文字列を取得
\def\Knapsack@getRestrictedTitles#1#2{%
  \@ifundefined{\Knapsack@prefix\Knapsack@restrictedTitles\the\numexpr#1\relax @\the\numexpr#2\relax}{}{\@nameuse{\Knapsack@prefix \Knapsack@restrictedTitles\the\numexpr#1\relax @\the\numexpr#2\relax}}%
}

%%% 「項目はi番目未満，値段上限値j」の下でカロリーの総和を最大化する項目の選び方を行ったときの値段使用量を取得
\def\Knapsack@getRestrictedPrice#1#2{%
  \@ifundefined{\Knapsack@prefix\Knapsack@restrictedPrice\the\numexpr#1\relax @\the\numexpr#2\relax}{0}{\@nameuse{\Knapsack@prefix \Knapsack@restrictedPrice\the\numexpr#1\relax @\the\numexpr#2\relax}}%
}

\def\Knapsack@relax{\relax}

%%% 「項目は#1番目未満，値段上限値#2」の下でカロリーの総和の最大値を#3に設定する。
%%% さらに，このときのカロリーの総和を最大化する項目の選び方のタイトル列は，「項目は#1-1番目まで，値段上限値#4」の下でのカロリーの総和を最大化する項目の選び方のタイトル列に，#5を加えた文字列に設定する。
%%% また，このときのカロリーの総和を最大化する項目の選び方を行ったときの値段使用量は，「項目は#1-1番目まで，値段上限値#4」の下でのカロリーの総和を最大化する項目の選び方を行ったときの値段使用量に，#6を加えた値に設定する。
\def\Knapsack@setIntermediateState#1#2#3#4#5#6{%
  % 最大カロリーの設定
  \expandafter\xdef\csname\Knapsack@prefix\Knapsack@restrictedCalorie\the\numexpr#1\relax @\the\numexpr#2\relax\endcsname{\the\numexpr#3\relax}%
  %
  % タイトルの連結作業
  \edef\Knapsack@oldTitle{\Knapsack@getRestrictedTitles{#1-1}{#4}}%
  \ifx\Knapsack@oldTitle\Knapsack@relax
    \let\Knapsack@oldTitle\@empty
  \fi
  \def\Knapsack@newTitle{#5}%
  \expandafter\xdef\csname\Knapsack@prefix\Knapsack@restrictedTitles\the\numexpr#1\relax @\the\numexpr#2\relax\endcsname{%
    \ifnum0\ifx\Knapsack@oldTitle\@empty1\fi\ifx\Knapsack@newTitle\@empty1\fi>0\relax
      \Knapsack@oldTitle\Knapsack@newTitle
    \else
      \Knapsack@oldTitle,\Knapsack@newTitle
    \fi
  }%
  %
  % タイトルの値段使用量の合算作業
  \edef\Knapsack@oldPrice{\Knapsack@getRestrictedPrice{#1-1}{#4}}%
  \ifx\Knapsack@oldPrice\Knapsack@relax
    \let\Knapsack@oldPrice\z@
  \fi
  \def\Knapsack@newPrice{#6}%
  \expandafter\xdef\csname\Knapsack@prefix\Knapsack@restrictedPrice\the\numexpr#1\relax @\the\numexpr#2\relax\endcsname{%
    \the\numexpr\Knapsack@oldPrice+\Knapsack@newPrice\relax
  }%
}

\def\KnapsackInputItems#1{%
  \setcounter{Knapsack@numberOfItems}{0}%
  \foreach \KnapsackItem in {#1} {%
    \expandafter\Knapsack@splitItems\KnapsackItem\relax
  }%
}

% \Knapsack{{タイトル1,カロリー1,値段1},{タイトル2,カロリー2,値段2},...,{タイトルn,カロリーn,値段n}}{値段上限値}
\def\Knapsack#1#2{%
  \global\advance\Knapsack@numberOfExecutions by \@ne
  \xdef\Knapsack@prefix{Knapsack\the\Knapsack@numberOfExecutions}%
  \KnapsackInputItems{#1}%
  %
  \foreach \i in {1,...,\the\c@Knapsack@numberOfItems} {%
    \foreach \j in {0,...,#2} {%
       % \Knapsack@c = c[i-1] %% i-1番目の項目の値段
       \Knapsack@c=\@nameuse{\Knapsack@prefix\Knapsack@price\the\numexpr\i-1\relax}\relax
       % \Knapsack@p = p[i-1] %% i-1番目の項目のカロリー
       \Knapsack@p=\@nameuse{\Knapsack@prefix\Knapsack@calorie\the\numexpr\i-1\relax}\relax
       % \Knapsack@B = m[i-1,j] %% 「項目はi-1番目未満，値段上限値j」の下でのカロリーの総和の最大値
       \Knapsack@B=\numexpr\Knapsack@getRestrictedCalorie{\i-1}{\j}\relax
       \unless\ifnum\Knapsack@c>\j\relax
          % \Knapsack@A = i-1 番目の項目をナップサックに入れた場合のカロリーの最大値
          \Knapsack@A=\numexpr\Knapsack@getRestrictedCalorie{\i-1}{\j-\Knapsack@c}+\Knapsack@p\relax
          \ifnum\Knapsack@A>\Knapsack@B\relax
            \Knapsack@setIntermediateState{\i}{\j}{\Knapsack@A}{\j-\Knapsack@c}{\@nameuse{\Knapsack@prefix\Knapsack@title\the\numexpr\i-1\relax}}{\Knapsack@c}%
          \else
            \Knapsack@setIntermediateState{\i}{\j}{\Knapsack@B}{\j}{}{0}%
          \fi
       \else
         \Knapsack@setIntermediateState{\i}{\j}{\Knapsack@B}{\j}{}{0}%
       \fi
    }%
  }%
  %
  \xdef\KnapsackMaimalCalorie{\Knapsack@getRestrictedCalorie{\the\c@Knapsack@numberOfItems}{#2}}%
  \xdef\KnapsackTitlesForMaximalCalorie{\Knapsack@getRestrictedTitles{\the\c@Knapsack@numberOfItems}{#2}}%
  \xdef\KnapsackTotalPriceForMaximalCalorie{\Knapsack@getRestrictedPrice{\the\c@Knapsack@numberOfItems}{#2}}%
}

%%% メニュー項目名，カロリー，値段のリスト
\def\KnapsackItems{%
{彩りガーデンサラダ,130,299},%
{小エビのサラダ,115,349},%
{やわらかチキンのサラダ,134,299},%
{わかめサラダ,92,299},%
{イタリアンサラダ,196,299},%
{シーフードサラダ,229,599},%
{半熟卵とポークのサラダ,433,599},%
{コーンクリームスープ,142,149},%
{冷たいパンプキンスープ（季節限定）,105,149},%
{たっぷり野菜のミネストローネ（季節限定）,222,299},%
{削りたてペコリーノチーズ,59,100},%
{ミニフィセル,188,169},%
{ガーリックトースト,252,189},%
{辛味チキン,374,299},%
{アスパラガスのオーブン焼き（季節限定）,221,299},%
{ポップコーンシュリンプ,215,299},%
{エスカルゴのオーブン焼き,256,399},%
{ムール貝のガーリック焼き,164,399},%
{野菜ソースのグリルソーセージ,570,399},%
{チョリソー,393,399},%
{柔らか青豆の温サラダ,213,199},%
{ほうれん草のソテー,138,199},%
{キャベツとアンチョビのソテー,80,199},%
{ポテトのグリル,366,199},%
{セロリのピクルス（季節限定）,52,199},%
{真イカのパプリカソース,138,199},%
{フォッカチオ,214,119},%
{プチフォッカ,214,139},%
{セットプチフォッカ,107,79},%
{フレッシュチーズとトマトのサラダ,203,299},%
{フレッシュチーズとトマトのサラダ（Wサイズ）,406,598},%
{プロシュート,162,399},%
{プロシュート（Wサイズ）,324,798},%
{熟成ミラノサラミ,95,299},%
{熟成ミラノサラミ（Wサイズ）,190,598},%
{マルゲリータピザ,568,399},%
{パンチェッタのピザ,646,399},%
{野菜ときのこのピザ,610,399},%
{やわらかイカのアンチョビのピザ,593,499},%
{バッファローモッツァレラのピザ,575,499},%
{ミラノサラミのピザ,606,499},%
{ほうれん草のグラタン（季節限定）,521,399},%
{シーフードグラタン,537,499},%
{アラビアータ,591,399},%
{ミートソースボロニア風,582,399},%
{半熟卵のミートソースボロニア風,672,468},%
{アーリオ・オーリオ,560,299},%
{キャベツのペペロンチーノ,686,399},%
{タラコソースシシリー風,605,399},%
{スープ入りトマト味ボンゴレ（季節限定）,686,499},%
{パルマ風スパゲッティ,700,399},%
{イカの墨入りスパゲッティ,610,499},%
{カルボナーラ,865,499},%
{アスパラガスとエビのクリームスパゲッティ（季節限定）,711,499},%
{アラビアータ（Wサイズ）,1182,770},%
{ミートソースボロニア風（Wサイズ）,1164,770},%
{アーリオ・オーリオ（Wサイズ）,1120,574},%
{キャベツのペペロンチーノ（Wサイズ）,1372,770},%
{タラコソースシシリー風（Wサイズ）,1210,770},%
{パルマ風スパゲッティ（Wサイズ）,1400,770},%
{イカの墨入りスパゲッティ（Wサイズ）,1220,976},%
{カルボナーラ（Wサイズ）,1730,976},%
{アスパラガスとエビのクリームスパゲッティ（季節限定）（Wサイズ）,1422,976},%
{トッピング半熟卵,90,69},%
{ミラノ風ドリア,542,299},%
{半熟卵のミラノ風ドリア,632,368},%
{セットプチフォッカ付きミラノ風ドリア,649,378},%
{いろどり野菜のミラノ風ドリア,590,399},%
{エビとイカのドリア,624,499},%
{シーフードパエリア,602,599},%
{エビと野菜のトマトクリームリゾット,302,399},%
{ハヤシ＆ターメリックライス,638,499},%
{半熟卵のハヤシ＆ターメリックライス,728,568},%
{ミックスグリル,823,599},%
{ハンバーグステーキ,514,399},%
{デミグラスソースのハンバーグ,628,499},%
{野菜ソースのハンバーグ（ディアボラ風）,585,499},%
{イタリアンハンバーグ,633,499},%
{焼肉とハンバーグの盛合せ,709,599},%
{若鶏のグリル（ディアボラ風）,541,499},%
{柔らかチキンのチーズ焼き,588,499},%
{パンチェッタと若鶏のグリル,663,599},%
{リブステーキ,621,999},%
{ライス,303,169},%
{ラージライス,454,219},%
{スモールライス,151,119},%
{カプチーノ（アイスケーキ）（季節限定）,114,199},%
{ティラミス（アイスケーキ）,131,199},%
{シナモンフォッカチオ,246,169},%
{プリンとカプチーノの盛合せ,330,399},%
{プリンとティラミスの盛合せ,347,399},%
{ミルクアイスのせシナモンフォッカチオ,346,319},%
{ミルクジェラート,100,199},%
{シチリア産レモンのソルベ,127,199},%
{イタリアンプリン,216,249},%
{チョコレートケーキ,166,299},%
{コーヒーゼリー,162,299},%
{トリフアイスクリーム,164,369}%
}
\def\KnapsackMaxPrice{1000}

\begin{document}

\begin{tcolorbox}[title=問題]
予算\KnapsackMaxPrice 円以内で，サイゼリヤで最大カロリーを摂取するような注文の仕方を求めよ。ただしサイゼリヤの料理のメニューは以下の通りとする。

\def\Knapsack@prefix{Knapsack}
\expandafter\KnapsackInputItems\expandafter{\KnapsackItems}

\begin{itemize}
  \foreach \i in {1,...,\the\c@Knapsack@numberOfItems} {%
    \item 
    \makebox[33zw][l]{\@nameuse{\Knapsack@prefix\Knapsack@title\the\numexpr\i-1\relax}}%
    \makebox[3zw][r]{\@nameuse{\Knapsack@prefix\Knapsack@price\the\numexpr\i-1\relax}円}%
    \makebox[6zw][r]{(\@nameuse{\Knapsack@prefix\Knapsack@calorie\the\numexpr\i-1\relax} kcal)}%
  }%
\end{itemize}
\end{tcolorbox}

\bigskip

\begin{tcolorbox}[title=解答]
\expandafter\Knapsack\expandafter{\KnapsackItems}{1000}%%% 問題を解く
\KnapsackTitlesForMaximalCalorie を選ぶと，経費\KnapsackTotalPriceForMaximalCalorie 円で，最大カロリー$\KnapsackMaimalCalorie\,\mathrm{kcal}$が得られる。
\end{tcolorbox}

\end{document}