Please help me with a "Knapsack Problem"

[kelyr]

Hi everyone, I really need your help. I'm working on a project that takes a lot of time. It's for accounts payable. This is done mostly and it usually has thousands of lines. The objective is to find debits that are made up of different credits (values on different cells) or viceversa.

I used the match formula to find exact amounts but still left a lot more that could not find because they are made of different values. I decided to use Solver to find the latter ones. What I realized is that it takes a lot of time to run the solver every time, so I’m not sure how more efficient that would be than looking them one by one. Also, with Solver, I cannot do more than 200 variables which led me to do this for every single day of the month which still takes up a lot of time. This is how my spreadsheet looks like right now:

DEBITS	CREDITS	Where?	MULTIPLIER	PRODUCT
$ -	$ -	1	0	$ -		Target:	$ 15,835.27
$ 18,808.13	$ -	44	0	$ -		Sum of Product	$ 15,835.27
$ 2,792.44	$ -	92	0	$ -		Difference	$ -
$ 843.50	$ -	86	0	$ -
$ -	$ -	1	0	$ -
$ 15,835.27	$ -	#N/A	0	$ -
$ 25.00	$ -	#N/A	0	$ -
$ -	$ -	1	0	$ -
$ -	$ -	1	0	$ -
$ -	$ -	1	0	$ -
$ -	$ 0.20	1	0	$ -
$ 0.20	$ -	11	0	$ -
$ 10,666.70	$ -	23	0	$ -
$ 214.15	$ -	#N/A	0	$ -
$ 244.50	$ -	#N/A	0	$ -
$ 250.11	$ -	#N/A	0	$ -
$ 379.50	$ -	#N/A	0	$ -
$ 475.50	$ -	#N/A	0	$ -
$ 479.84	$ -	#N/A	0	$ -
$ 3,053.66	$ -	#N/A	0	$ -
$ 46,658.71	$ -	84	0	$ -
$ -	$ 15,939.00	1	0	$ -
$ -	$ 10,666.70	1	0	$ -
$ -	$ 9,885.36	1	0	$ -
$ -	$ 1,877.84	1	0	$ -
$ -	$ 729.95	1	0	$ -
$ 63.07	$ -	#N/A	0	$ -
$ 509.09	$ -	61	0	$ -
$ 1,471.95	$ -	#N/A	0	$ -
$ -	$ 6,407.32	1	0	$ -
$ -	$ 2,430.99	1	1	$ 2,430.99
$ -	$ 1,730.00	1	0	$ -
$ -	$ 44.04	1	1	$ 44.04
$ 6,380.55	$ -	45	0	$ -
$ -	$ 633.00	1	0	$ -
$ 477.43	$ -	62	0	$ -
$ -	$ 1,640.45	1	0	$ -
$ 35.06	$ -	#N/A	0	$ -
$ 247.08	$ -	#N/A	0	$ -
$ 909.41	$ -	#N/A	0	$ -
$ 2,148.85	$ -	#N/A	0	$ -
$ 44.04	$ -	33	0	$ -
$ 6,557.37	$ -	#N/A	0	$ -
$ -	$ 18,808.13	1	0	$ -
$ -	$ 6,380.55	1	0	$ -
$ 192.92	$ -	#N/A	0	$ -
$ 250.39	$ -	#N/A	0	$ -
$ 287.65	$ -	#N/A	0	$ -
$ 348.97	$ -	#N/A	0	$ -
$ 400.09	$ -	#N/A	0	$ -
$ 434.35	$ -	#N/A	0	$ -
$ 445.45	$ -	#N/A	0	$ -
$ 534.57	$ -	#N/A	0	$ -
$ 575.85	$ -	#N/A	0	$ -
$ 601.55	$ -	#N/A	0	$ -
$ 2,947.85	$ -	59	0	$ -
$ 9,885.36	$ -	24	0	$ -
$ -	$ 8,105.98	1	1	$ 8,105.98
$ -	$ 2,947.85	1	1	$ 2,947.85
$ -	$ 1,644.27	1	1	$ 1,644.27
$ -	$ 509.09	1	0	$ -
$ -	$ 477.43	1	1	$ 477.43
$ -	$ 82.06	1	1	$ 82.06
$ 50.00	$ -	#N/A	0	$ -
$ 82.06	$ -	63	0	$ -
$ 225.99	$ -	#N/A	0	$ -
$ 425.00	$ -	87	0	$ -
$ 464.83	$ -	#N/A	0	$ -
$ 931.42	$ -	#N/A	0	$ -
$ 1,680.00	$ -	#N/A	0	$ -
$ 2,411.95	$ -	#N/A	0	$ -
$ -	$ 202.24	1	0	$ -
$ -	$ 102.65	1	1	$ 102.65
$ 47.95	$ -	#N/A	0	$ -
$ 192.95	$ -	#N/A	0	$ -
$ 633.00	$ -	35	0	$ -
$ 1,399.55	$ -	#N/A	0	$ -
$ 13,424.43	$ -	#N/A	0	$ -
$ 15,706.01	$ -	#N/A	0	$ -
$ -	$ 340.49	1	0	$ -
$ -	$ 1,859.16	1	0	$ -
$ 102.65	$ -	73	0	$ -
$ 6,407.32	$ -	30	0	$ -
$ -	$ 46,658.71	1	0	$ -
$ -	$ 39,844.22	1	0	$ -
$ -	$ 843.50	1	0	$ -
$ -	$ 425.00	1	0	$ -
$ 35.06	$ -	#N/A	0	$ -
$ 196.87	$ -	#N/A	0	$ -
$ 1,627.23	$ -	#N/A	0	$ -
$ 1,644.27	$ -	60	0	$ -
$ -	$ 2,792.44	1	0	$ -
$ -	$ 1,899.25	1	0	$ -
$ 38.22	$ -	#N/A	0	$ -
$ 63.07	$ -	#N/A	0	$ -
$ 100.95	$ -	#N/A	0	$ -
$ -	$ 22.89	1	0	$ -
$ 54.10	$ -	#N/A	0	$ -
$ 271.99	$ -	#N/A	0	$ -
$ 937.56	$ -	#N/A	0	$ -
$ 1,573.16	$ -	#N/A	0	$ -
$ 5.00	$ -	#N/A	0	$ -
$ 8.40	$ -	#N/A	0	$ -
$ 9.49	$ -	#N/A	0	$ -
$ 39,844.22	$ -	85	0	$ -
$ 95.27	$ -	#N/A	0	$ -
$ 285.19	$ -	#N/A	0	$ -
$ 10,934.18	$ -	#N/A	0	$ -
$ 15,939.00	$ -	22	0	$ -
				$ 15,835.27

<colgroup><col width="91" style="width: 68pt;"><col width="144" style="width: 108pt;"><col width="79" style="width: 59pt;"><col width="123" style="width: 92pt;"><col width="101" style="width: 76pt;"><col width="71" style="width: 53pt;"><col width="109" style="width: 82pt;"><col width="101" style="width: 76pt;"><col width="71" style="width: 53pt;"></colgroup><tbody>
</tbody>

I read and copied that code from this macro https://www.mrexcel.com/challenges/accounts-receivable-challenge/ but it didn't work for me.

Thank you so much for your help, I appreciate it a bunch!!

 

[shg]

The good news is, you don't have to solve this problem, because it's unsolvable.

People describe the problem of receiving payments that do not specify the invoices they cover, and so they want to fund the combination that meets the payment total. It is, in general, not a solvable problem. Here’s why.

From Wikipedia:

In mathematics, the pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item.[1] This theorem is exemplified in real life by truisms like "there must be at least two left gloves or two right gloves in a group of three gloves". It is an example of a counting argument, and despite seeming intuitive it can be used to demonstrate possibly unexpected results.
This is one of those unexpected results.

Let N = the number of invoices and A = the average values of all invoices. Consider the simple case of N = 50 invoices averaging $100 each. Then the total of all invoices is N * A = 50 * 100 = $5000. That means that every subset of invoices must total somewhere between $0.01 (if there were a one-penny invoice) and $5000.00. Considering that the penny is the smallest unit of US currency, that means there are exactly 100*5000 = 50,000 different totals possible. In general, there are 100*N*A pigeonholes, and the sum of every combination of invoices matches one of those pigeonholes.

In any combination of invoices, every individual invoice either is or isn’t a member of that combination. That means there are 2^N combinations of invoices, each including somewhere between none and all of the invoices. Here, there are 2^50, which is about 10^15.

So the sum of each combination is a pigeon, and each of those pigeons fits in one those pigeonholes. What’s the average occupancy of a pigeonhole? Here comes that counterintuitive result:

For any random total you choose, there are an average of 2 billion combinations of invoices that give that result, down to the penny. Some totals will have fewer, some will have more, but that’s the average. The problem is not that you can’t find one, it’s that you find a zillion.

That's just for 50 numbers and you've got thousands.

 

[shg]

If you think that's not true because your average invoice is much larger than that, then suppose that you're Boeing, selling commercial airliners, and your average invoice is $100M. With those same 50 items,

Number of Invoices:​	50​	B1: Input
Average Invoice Amount:​	$ 100,000,000.00​	B2: Input
Combinations:​	1,125,899,906,842,620​	B3: =2^B1
Number of possible sums​	500,000,000,000​	B4: =B1*B2*100
Average Pigeonhole Occupancy​	2251.8​	B5: =B3/B4

There are, on average, over 2000 ways to arrive at any given total.

 

[kelyr]

Thank you, I appreciate it!