Please help me with a "Knapsack Problem"

kelyr

New Member
Joined
Jun 16, 2018
Messages
3
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?MULTIPLIERPRODUCT
$ - $ - 10 $ - Target: $ 15,835.27
$ 18,808.13 $ - 440 $ - Sum of Product $ 15,835.27
$ 2,792.44 $ - 920 $ - Difference $ -
$ 843.50 $ - 860 $ -
$ - $ - 10 $ -
$ 15,835.27 $ - #N/A0 $ -
$ 25.00 $ - #N/A0 $ -
$ - $ - 10 $ -
$ - $ - 10 $ -
$ - $ - 10 $ -
$ - $ 0.20 10 $ -
$ 0.20 $ - 110 $ -
$ 10,666.70 $ - 230 $ -
$ 214.15 $ - #N/A0 $ -
$ 244.50 $ - #N/A0 $ -
$ 250.11 $ - #N/A0 $ -
$ 379.50 $ - #N/A0 $ -
$ 475.50 $ - #N/A0 $ -
$ 479.84 $ - #N/A0 $ -
$ 3,053.66 $ - #N/A0 $ -
$ 46,658.71 $ - 840 $ -
$ - $ 15,939.00 10 $ -
$ - $ 10,666.70 10 $ -
$ - $ 9,885.36 10 $ -
$ - $ 1,877.84 10 $ -
$ - $ 729.95 10 $ -
$ 63.07 $ - #N/A0 $ -
$ 509.09 $ - 610 $ -
$ 1,471.95 $ - #N/A0 $ -
$ - $ 6,407.32 10 $ -
$ - $ 2,430.99 11 $ 2,430.99
$ - $ 1,730.00 10 $ -
$ - $ 44.04 11 $ 44.04
$ 6,380.55 $ - 450 $ -
$ - $ 633.00 10 $ -
$ 477.43 $ - 620 $ -
$ - $ 1,640.45 10 $ -
$ 35.06 $ - #N/A0 $ -
$ 247.08 $ - #N/A0 $ -
$ 909.41 $ - #N/A0 $ -
$ 2,148.85 $ - #N/A0 $ -
$ 44.04 $ - 330 $ -
$ 6,557.37 $ - #N/A0 $ -
$ - $ 18,808.13 10 $ -
$ - $ 6,380.55 10 $ -
$ 192.92 $ - #N/A0 $ -
$ 250.39 $ - #N/A0 $ -
$ 287.65 $ - #N/A0 $ -
$ 348.97 $ - #N/A0 $ -
$ 400.09 $ - #N/A0 $ -
$ 434.35 $ - #N/A0 $ -
$ 445.45 $ - #N/A0 $ -
$ 534.57 $ - #N/A0 $ -
$ 575.85 $ - #N/A0 $ -
$ 601.55 $ - #N/A0 $ -
$ 2,947.85 $ - 590 $ -
$ 9,885.36 $ - 240 $ -
$ - $ 8,105.98 11 $ 8,105.98
$ - $ 2,947.85 11 $ 2,947.85
$ - $ 1,644.27 11 $ 1,644.27
$ - $ 509.09 10 $ -
$ - $ 477.43 11 $ 477.43
$ - $ 82.06 11 $ 82.06
$ 50.00 $ - #N/A0 $ -
$ 82.06 $ - 630 $ -
$ 225.99 $ - #N/A0 $ -
$ 425.00 $ - 870 $ -
$ 464.83 $ - #N/A0 $ -
$ 931.42 $ - #N/A0 $ -
$ 1,680.00 $ - #N/A0 $ -
$ 2,411.95 $ - #N/A0 $ -
$ - $ 202.24 10 $ -
$ - $ 102.65 11 $ 102.65
$ 47.95 $ - #N/A0 $ -
$ 192.95 $ - #N/A0 $ -
$ 633.00 $ - 350 $ -
$ 1,399.55 $ - #N/A0 $ -
$ 13,424.43 $ - #N/A0 $ -
$ 15,706.01 $ - #N/A0 $ -
$ - $ 340.49 10 $ -
$ - $ 1,859.16 10 $ -
$ 102.65 $ - 730 $ -
$ 6,407.32 $ - 300 $ -
$ - $ 46,658.71 10 $ -
$ - $ 39,844.22 10 $ -
$ - $ 843.50 10 $ -
$ - $ 425.00 10 $ -
$ 35.06 $ - #N/A0 $ -
$ 196.87 $ - #N/A0 $ -
$ 1,627.23 $ - #N/A0 $ -
$ 1,644.27 $ - 600 $ -
$ - $ 2,792.44 10 $ -
$ - $ 1,899.25 10 $ -
$ 38.22 $ - #N/A0 $ -
$ 63.07 $ - #N/A0 $ -
$ 100.95 $ - #N/A0 $ -
$ - $ 22.89 10 $ -
$ 54.10 $ - #N/A0 $ -
$ 271.99 $ - #N/A0 $ -
$ 937.56 $ - #N/A0 $ -
$ 1,573.16 $ - #N/A0 $ -
$ 5.00 $ - #N/A0 $ -
$ 8.40 $ - #N/A0 $ -
$ 9.49 $ - #N/A0 $ -
$ 39,844.22 $ - 850 $ -
$ 95.27 $ - #N/A0 $ -
$ 285.19 $ - #N/A0 $ -
$ 10,934.18 $ - #N/A0 $ -
$ 15,939.00 $ - 220 $ -
$ 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!!
 

Some videos you may like

Excel Facts

Why are there 1,048,576 rows in Excel?
The Excel team increased the size of the grid in 2007. There are 2^20 rows and 2^14 columns for a total of 17 billion cells.

shg

MrExcel MVP
Joined
May 7, 2008
Messages
21,770
Office Version
  1. 2010
Platform
  1. Windows
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

MrExcel MVP
Joined
May 7, 2008
Messages
21,770
Office Version
  1. 2010
Platform
  1. Windows
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.
 

Watch MrExcel Video

Forum statistics

Threads
1,109,341
Messages
5,528,146
Members
409,802
Latest member
joeino

This Week's Hot Topics

  • Change military grades into rank
    Afternoon all Need help with formula that will change military rank (i.e. 1, 2, 3 into Amn, A1C, SrA). Running IF formula that does not work...
  • VBA COUNTIF SOLUTION
    Hi The following are the errors spread across the several columns from E to Q ie. 13 columns across several sheets with more than 500 rows per...
  • INSERT ROW WITH SPECIFIS TEXT IN A COLUMN
    Hi All! How can identify that that the row to be inserted has to be inserted before 1st row with specific text in column F. If I record the...
  • Auto-Create a monthly Sign in sheet for preschool students
    The image below is what each page looks like. Above is space for the "Child Name" "Month" "Class" School days are obviously Monday-Friday but...
  • VBA vlookup multiple results
    Hi folks, Hopefully someone out there can help. I have a list to vlookup which works (ish). the lookup only picks up the first instance of the...
  • Extract values for earliest/latest times
    I am trying to put together a formula to get the earliest start time, the latest end time from column A for each person in Column B-F without the...
Top