In a Stock Broking business (Firm), Customers deposit margin money through cheques. Although cheques are received from customers at branches, clearing (realization) of the same normally takes 3-4 days. On one hand, the Firm wishes to allow trading to the customers against the deposited cheques from the day it receives the cheque, on other hand there is a risk associated with this i.e cheque may get dishonored and the Firm may incur huge financial losses because of allowing customers to trade in anticipation of the cheque realization. Hence, there is a trade off between customer centricity & Financial Risk management.

The Firm may decide to take a calculated risk in order to retain its customer centric approach (it is a delightful experience for customers if they get trading benefit against the deposited cheque instantly before realization). The Firm may decide to give the benefit of cheque which are below a set threshold amount (say 50,000) instantly and for cheques which are above threshold amount the credit will be given only after realization. Sometimes there are multiple unrealized cheques deposited by one client but the Firm needs to cap the total benefit of unrealized cheques to 50,000 (partial benefit against any cheque is not possible i.e. either a cheque will be considered in full or not considered) E.g. if a customer deposits 3 cheques of 40,000 each then also the total instant benefit against all unrealized cheques shall be capped at 50,000 - hence only one cheques of 40,000 will be credited to customers ledger before realization.

Now the question here is with respect to selection of cheques to give best results i.e. maximum total below 50,000. Consider the following example:

Cheque1: 55,000

Cheque2: 44,000

Cheque3: 28,000

Cheque4: 7,000

Cheque5: 6,500

Cheque6: 4,000

Cheque7: 3,000

Cheque8: 500

The Firm wants to identify the "Combination of cheques" which gives the maximum benefit to the Customer subject to a limit of 50,000. The result should be cheques 3-8. They add up to 49,000.

Here's another example:

Cheque1: 55,000

Cheque2: 45,000

Cheque3: 25,000

Cheque4: 5,000

The result here should be cheque 2 and 4. They add up to 50,000.

Here are my thoughts:

1. I have assumed that the total number of cheques received from customer will be capped to 8. This limit can be relaxed but processing will then take time.

2. Create all possible combinations of cheques which can be credited. So, since no partial credit is allowed, the cheque can either be accepted in full or be rejected. Hence the possible values can be 2 i.e. 1 (Accepted) or 0 (Rejected).

3. So if there are 8 cheques received from a certain customer, then there will be 2^8 i.e. 256 possible combinations. This can also be computed by using the =PERMUTATIONA(2,8) formula. I'd like to than Saurabh Gupta for sharing the formula to generate all these combinations.

4. After creating all possible combinations, add the cheque amount for each combination.

5. Scan this total column and highlight the one which is the largest value <= the threshold value i.e. 50,000.

You may refer to my solution in the Solution worksheet of this workbook.