Story problem: Propose formula to derive cheapest price

[copp3r]

Goal : To spend the least amount of cash

There are 6 types of groceries to buy in the supermarket (A, B, C, D, E, F).
Each costs $0.15 per item.
A shopper can choose to pay based on individual price, or he can buy vouchers if it's cheaper. There's a limit to how many each vouchers you can buy (each type has different limit).
The available vouchers are:

Voucher	Eligible grocery type	Voucher price	Grocery quantity per voucher	Max voucher available
V0	All 6	$ 0	50	1
V1	All 6	$ 10	100	5
V2	A, B	$ 10	Unlimited	1
V3	A, B, C, D	$ 10	500	5
V4	A, C, E	$ 10	250	5

Propose formula to find :
a) the best combination of vouchers to achieve minimum cost
b) the minimum cost

I've spent the whole evening trying to crack this. Either there's no real solution for it, or i'm just not smart enough. I'm really hoping for the latter... Anyone can point me to the right direction?

 

[Unknown008]

Well, to begin with you need to know how much of each you need.

If you don't need any A or B, voucher V2 is useless.
If you need a little of each, voucher V0 is the best.

I would say there might be a formula for some value of a, b, c, d, e and f representing the number of each grocery you need and the values V0, V1, V2, V3 and V4 representing the vouchers and giving a minimum cost, but I really don't find the point, without knowing the exact goal (i.e. what to buy and how many)

 

[copp3r]

I tinkered with the problem further, and have a proposed solution. (btw, does this belong to the Algebra forum..? )
I don't know if this gets the cheapest price. So do highlight if you can suggest a better approach

i) We want to use the voucher that can result in the highest savings. So rank the (paid) vouchers from cheapest to most expensive.
ii) When we use each voucher, we need to decide which grocery type we'd use it on (necessary if quantity > what voucher can cover). If an item cannot be covered by the "lower" voucher, it should be paid for first.

Voucher	Grocery types that the voucher can cover, ranked from which to be paid for first. () means sequence doesn't matter	Voucher price	Grocery quantity that 1 voucher can cover	Max available number of each voucher type
V2	(A, B)	$ 10	Unlimited	1
V3	(B, D), (A, C)	$ 10	500	5
V4	(A, C, E)	$ 10	250	5
V1	all	$ 10	100	5
V0	all	0	50	1

iii) A voucher is worth buying if the number of groceries is > voucher price/item price + V0's coverage = $10/$0.15 + 50 = 126.7

iv) CAPACITY Vx = the smaller value between "sum of all remaining groceries in your cart the voucher can pay" AND "grocery quantity that a type of voucher can cover as stated in table above"
So for V4, the value is the smaller between (A + C + E) and 250.

v) See table and follow sequence from V2 to V3 to V4 ...

Voucher	Process	Price
V2	If CAPACITY V2 = MAX (the most) compared to all voucher groups, and it's also >500, then buy V2 and adjust the value of A, B. Else go to V3.	$10 x quantity
V3	If CAPACITY V3 = MAX, and also > 126.7, then buy V3 and adjust the remaining value of B, D, A, C. Can repeat the above step 5 times (because there are 5 vouchers). If the above check do not hold anymore, go to V4.	$10 x quantity
V4	If CAPACITY V4 = MAX, and also > 126.7, then buy V4 and adjust the remaining value of A, C, E. Can repeat the above step 5 times (because there are 5 vouchers). If the above check do not hold anymore, go to V1	$10 x quantity
V1	If CAPACITY V1 > 126.7, then buy V1 and adjust the remaining values. Can repeat the above step 5 times (because there are 5 vouchers). If the above check do not hold anymore, go to V0.	$10 x quantity
V0	If "remaining >= 50, then extra cash = (remaining - 50) * 0.15, else 0	(remaining item - 50) * 0.15

 

[copp3r]

The story problem is not from school. It's a real life scenario that i simplified into the question above.
You may have missed one constraint. There's a limit to how many times we can use a voucher type.
For example, V₀ can only be bought 1 time.

 

[Unknown008]

If it's a real life problem, I would indeed suggest you work out with a new solution each time your budget changes instead of spending so much time to look for a general solution. Plus with things often changing, this might be the most time effective method.

Otherwise, your solution has the first issue:

For V0, you said buy it for anything less than a total of 127.6.
Case Study: You have 125 items (total and specific items not specified)

Your option: V0 for first 50, then buy the rest at regular price.
50 -> Free
75 -> (75*0.15) = $11.25

My option: V0 for first 50, then V1 for the rest.
50 -> Free
75 -> With voucher, I get a total of $10.

Savings: $1.25

The 'gap change' here occurs at 66.6 when the price per item is estimated to be 0.15.

\(\displaystyle 0.15 = \frac{10}{Num}\)

\(\displaystyle Num = \frac{10}{0.15} = 66.7\)

And you round down, to 66.

So, if {V <= 66} {Get V0, then buy at 0.15 each}
else {Get V0 then V1}

Now, we know that if you get too large, you will need to get another voucher, but then, depending on what item you need, you might want to switch V3 or V4, except if it involves item F. But assuming you don't want to change, you will have to stop at 100 to do V0, 1 of V1 and the rest at 0.15; and when you reach total = 134, you switch to V0, and 2 of V1.

It gets branched off too much for a daily situation and as said earlier, a day-to-day assessment would be way easier.

 

[copp3r]

Thanks for the effort, guys!