select subset of combinations based on condition

Question

My question is about choosing a subset of combinations within a list, based on a condition.

Fot example, a shop sells 26 products. The name of a product starts with a letter. Each product has a price. For example, the customer pays 1 dollar for product 'a'. The product-price range for this shop looks like:

shop = {{a, 1}, {b, 2}, {c, 3}, {d, 4}, {e, 5}, {f, 6}, {g, 7}, {h, 
   8}, {i, 9}, {j, 10}, {k, 11}, {l, 12}, {m, 13}, {n, 14}, {o, 
   15}, {p, 16}, {q, 17}, {r, 18}, {s, 19}, {t, 20}, {u, 21}, {v, 
   22}, {w, 23}, {x, 24}, {y, 25}, {z, 26} };

A customers visit a store with 30 dollar in his pocket.The customer wants to know all combinations of products he can buy for 30 dollar, or less.

For example: {{z, 26},{d, 4}},{{z, 26},{c, 3}},{{z, 26},{b, 2}}....{{j, 10},{t, 20}}

I tried to use 'Subsets' to find als possible combinations. Then I get a error:

test = Subsets[shop];
test1 = {#, Sum[i, {i, #}]} & /@ test;
Select[test1[[All, 2]][[2 ;; -1]], #[[2]] < 30 &]

$RecursionLimit::reclim2: Recursion depth of 1024 exceeded during evaluation.

When I made a smaller selection (for example the first 8 products) it works fine.

test = Subsets[shop[[1 ;; 8]]];
test1 = {#, Sum[i, {i, #}]} & /@ test;
Select[test1[[All, 2]][[2 ;; -1]], #[[2]] < 30 &]

Who has a solution for this problem? Or a different approach?

Answer 1

The key part here is using FrobeniusSolve.

shop = {{a,1},{b,2},{c,3},{d,4},{e,5},{f,6},{g,7},{h,8},{i,9},{j,10},{k,11},{l,12},{m,13},{n,14},{o,15},{p,16},{q,17},{r,18},{s,19},{t,20},{u,21},{v,22},{w,23},{x,24},{y,25},{z,26}};

money = 30;
(*All combos with possibly multiple of each*)FrobeniusSolve[shop[[;; , 2]], money];
(*If the store only has one of each item*) Pick[shop, #, 1] & /@ Select[%, Max[#]==1 &]

{{{n, 14}, {p, 16}}, {{m, 13}, {q, 17}}, <<288>>, {{a, 1}, {b, 2}, {c, 3}, {d, 4}, {e, 5}, {f, 6}, {i, 9}}}