How do I ask a teller for money at the bank?
JavaScript (ES6), 485 476 bytes

Alright ... this is a monster. :-(
But it's a rather fast monster that solves all test cases almost instantly.

I may attempt some more advanced golfing later, but I've already spent far too much time on it.

f=(b,a,L=[...a])=&gt;L.reduce((a,x)=&gt;[...a,...a.map(y=&gt;[x,...y])],[[]]).sort((a,b)=&gt;a[b.length]||-1).find(L=&gt;(Y=G(U(b)-U(L),L.sort((a,b)=&gt;a-b)),Y[0]&amp;&amp;!Y.some(a=&gt;P(b.map(a=&gt;G(a,[]))).every(b=&gt;b+''!=a))),U=a=&gt;~~eval(a.join`+`),P=(e,C=[],R=[])=&gt;e[0].map(v=&gt;R=(c=v.map((x,i)=&gt;x+(C[i]|0)),e[1])?[...P(e.slice(1),c),...R]:[c,...R])&amp;&amp;R,G=(n,l)=&gt;(S=[],g=(n,l)=&gt;n?a.map(x=&gt;x&lt;l[0]|x&gt;n||g(n-x,[x,...l])):S=[l.map(v=&gt;s[a.indexOf(v)]++,s=[...a].fill(0))&amp;&amp;s,...S])(n,l)&amp;&amp;S)||f(b,a,[...a,...L])


Test cases



f=(b,a,L=[...a])=&gt;L.reduce((a,x)=&gt;[...a,...a.map(y=&gt;[x,...y])],[[]]).sort((a,b)=&gt;a[b.length]||-1).find(L=&gt;(Y=G(U(b)-U(L),L.sort((a,b)=&gt;a-b)),Y[0]&amp;&amp;!Y.some(a=&gt;P(b.map(a=&gt;G(a,[]))).every(b=&gt;b+''!=a))),U=a=&gt;~~eval(a.join`+`),P=(e,C=[],R=[])=&gt;e[0].map(v=&gt;R=(c=v.map((x,i)=&gt;x+(C[i]|0)),e[1])?[...P(e.slice(1),c),...R]:[c,...R])&amp;&amp;R,G=(n,l)=&gt;(S=[],g=(n,l)=&gt;n?a.map(x=&gt;x&lt;l[0]|x&gt;n||g(n-x,[x,...l])):S=[l.map(v=&gt;s[a.indexOf(v)]++,s=[...a].fill(0))&amp;&amp;s,...S])(n,l)&amp;&amp;S)||f(b,a,[...a,...L])

console.log(JSON.stringify(f([22,8], [1,2,5,10,20,50])))
console.log(JSON.stringify(f([2,1,2], [1,5])))
console.log(JSON.stringify(f([20,10], [1,2,5,10,20,50])))
console.log(JSON.stringify(f([1,1,1,1], [1,2])))
console.log(JSON.stringify(f([20,6], [1,4,5])))
console.log(JSON.stringify(f([2,6], [1,2,7])))
console.log(JSON.stringify(f([22,11], [1,3,30,50])))
console.log(JSON.stringify(f([44,22], [1,3,30,50])))




How?

NB: This is not matching the current version anymore, but is much easier to read that way.

// b = list of payments, a = list of bills,
// L = list from which the requested bills are chosen
f = (b, a, L = [...a]) =&gt; (
  // U = helper function that computes the sum of an array
  U = a =&gt; ~~eval(a.join`+`),

  // P = function that computes the summed Cartesian products of arrays of integers
  // e.g. P([[[1,2],[3,4]], [[10,20],[30,40]]]) --&gt; [[33,44], [13,24], [31,42], [11,22]]
  P = (e, C = [], R = []) =&gt; e[0].map(v =&gt; R =
    (c = v.map((x, i) =&gt; x + (C[i] | 0)), e[1]) ? [...P(e.slice(1), c), ...R] : [c, ...R]
  ) &amp;&amp; R,

  // G = function that takes a target amount and a list of requested bills and returns
  // all combinations that contain the requested bills and add up to this amount;
  // each combination is translated into a list of number of bills such as [2,0,0,1,0]
  G = (n, l) =&gt; (
    S = [],
    g = (n, l) =&gt; n ?
      a.map(x =&gt; x &lt; l[0] | x &gt; n || g(n - x, [x, ...l])) :
      S = [l.map(v =&gt; s[a.indexOf(v)]++, s = [...a].fill(0)) &amp;&amp; s, ...S]
  )(n, l) &amp;&amp; S,

  // compute X = list of possible bill combinations to process all payments
  X = P(b.map(a =&gt; G(a, []))),

  // compute the powerset of L and sort it from shortest to longest list
  L.reduce((a, x) =&gt; [...a, ...a.map(y =&gt; [x, ...y])], [[]])
  .sort((a, b) =&gt; a[b.length] || -1)

  .find(L =&gt; (
    // compute Y = list of possible combinations to reach the total amount,
    // using the requested bills
    Y = G(U(b) - U(L), L.sort((a, b) =&gt; a - b)),

    // exit if Y is not empty and all combinations in Y allow to generate all payments
    Y[0] &amp;&amp; !Y.some(a =&gt; X.every(b =&gt; b + '' != a)))
  )

  // if no solution was found, enlarge the set of requested bills and try again
  || f(b, a, [...a, ...L])
)