expl3：単価が異なるお菓子をどういう組み合わせで買えば目標の合計値になるか問題

okashi.tex

% upLaTeX文書
\documentclass[uplatex,a4paper]{jsarticle}
\usepackage{xparse}
\ExplSyntaxOn

\int_new:N \l_xx_total_int
\clist_new:N \l_xx_price_clist
\prop_new:N \l_xx_count_prop
\bool_new:N \l_xx_solved_bool
\int_new:N \l_xx_instid_int
\int_new:N \l_xx_size_int
\int_new:N \l_xx_price_int

\NewDocumentCommand \Okashi { m m }
  {
    \int_set:Nn \l_xx_total_int {#1}
    \clist_set:Nn \l_xx_price_clist {#2}
    \xx_solve:
    \xx_print_solution:n {#1}
    
  }

\cs_new:Nn \xx_print_solution:n
  {
    \bool_if:NTF \l_xx_solved_bool
      {
        \int_step_inline:nnn { 1 } { \l_xx_size_int }
          {
            \prop_get:NnN \l_xx_count_prop {##1} \l_tmpa_tl
            \clist_item:Nn \l_xx_price_clist {##1}
            円のが \l_tmpa_tl 個
            \int_compare:nNnF {##1} = { \l_xx_size_int } { 、 }
          }
        で
        \int_eval:n {#1}
        円になる。
      }
      { 解が見つかりません。 }
  }

\cs_new:Nn \xx_solve:
  {
    \int_set:Nn \l_xx_size_int { \clist_count:N \l_xx_price_clist }
    \int_step_inline:nnn { 1 } { \l_xx_size_int }
      {
        \int_add:Nn \l_xx_total_int { - \clist_item:Nn \l_xx_price_clist {##1} }
        \prop_put:Nnn \l_xx_count_prop {##1} { 1 }
      }
    \int_compare:nNnTF { \l_xx_total_int } < { 0 }
      { \bool_set_false:N \l_xx_solved_bool }
      { % always declare a new intarray
        \int_incr:N \l_xx_instid_int
        \exp_args:Nc \xx_solve_aux:N { g_xx_price_ \int_to_arabic:n { \l_xx_instid_int } _intarray }
      }
  }

\cs_new:Nn \xx_solve_aux:N
  {
    \intarray_new:Nn #1 { \l_xx_total_int }
    \cs_set:Npn \xx_array_get:n { \intarray_item:Nn #1 }
    \cs_set:Npn \xx_array_set:nn { \intarray_gset:Nnn #1 }
    \int_step_function:nnN { 1 } { \l_xx_size_int } \xx_one_item:n
    \int_compare:nNnTF { \xx_array_get:n {\l_xx_total_int} } = { 0 }
      { \bool_set_false:N \l_xx_solved_bool }
      {
        \xx_pick_item:
        \bool_set_true:N \l_xx_solved_bool
      }
  }

\cs_new:Nn \xx_one_item:n
  {
    \int_set:Nn \l_xx_price_int { \clist_item:Nn \l_xx_price_clist {#1} }
    \int_step_inline:nnn { \l_xx_price_int } { \l_xx_total_int }
      {
        \bool_lazy_and:nnT
          { \int_compare_p:nNn { \xx_array_get:n {##1} } = { 0 } }
          {
            \bool_lazy_or_p:nn % index must not be zero
              { \int_compare_p:nNn { ##1 } = { \l_xx_price_int } }
              { \int_compare_p:nNn { \xx_array_get:n { ##1 - \l_xx_price_int } } > { 0 } }
          }
          { \xx_array_set:nn {##1} {#1} }
      }
  }

\cs_new:Nn \xx_pick_item:
  {
    \int_do_while:nNnn { \l_xx_total_int } > { 0 }
      {
        \int_set:Nn \l_tmpa_int { \xx_array_get:n { \l_xx_total_int } }
        \int_add:Nn \l_xx_total_int { - \clist_item:Nn \l_xx_price_clist { \l_tmpa_int } }
        \prop_get:NVN \l_xx_count_prop \l_tmpa_int \l_tmpa_tl
        \int_set:Nn \l_tmpb_int { \l_tmpa_tl + 1 }
        \prop_put:NVV \l_xx_count_prop \l_tmpa_int \l_tmpb_int
      }
  }

\ExplSyntaxOff
\begin{document}

\Okashi{3000}{146,172,400,500}

\Okashi{9731}{146,172,400,500}

%時間かかるけど解けた
%\Okashi{129414}{146,172,400,500}

\end{document}

元ネタ→単価が異なるお菓子をどういう組み合わせで買えば目標の合計値になるか問題

「xpl3のプログラムを読む練習(?)がしたいけど、中のロジックがよくわからん」
という人のために、ほぼ同じ内容をLuaで書いたのを用意した→Lua版