I'm looking for an algorithm, which can solve the following problem:
There is a basket, containing (n) products, paired with a value, which shows how much money is required to cover them.
E.g basket(n=3): {apple,500€},{banana,400€},{cherry,300€}
In our purse we have different type of vouchers(m pcs) in different amount. A voucher is a payment method, which has a value, and can be used to pay predefined products, not necessarily all types of them. It is also given which products can we pay with one voucher and vica-versa.
E.g: Voucher types:
V1 can be used to pay: apple,cherry
V2 can be used to pay: apple,banana
V3 can be used to pay: cherry
E.g purse(m=3): {V1,500€},{V2,600€},{V3,100€}
We would like to pay the whole basket, so a voucher can be used to cover more products. Meanwhile more money than required to pay the basket can be accepted. The sum of the basket, and the payment are natural numbers. The task is to decide whether are we able to pay the basket used the given purse?
Does anyone can suggest an algorithm or a reduction to a well-known problem to solve this decision problem properly in every case?
Thank you,
Adam
If all prices and values are natural numbers, you are looking for a perfect matching: There's a node for every Euro of fruit, a node for every Euro of vvouvher value and an edge from each vouvher-Euro-node to each compatible fruit-euto-node.