Return Combination of Records Based on Best Match With Additional Criteria (1 Viewer)

Hasslehump

New member
Local time
Today, 03:20
Joined
May 16, 2020
Messages
4
I have a problem that I admit, I do not know where to even begin to resolve.
My requirement is to return a combination of records that will fit when combined together as a closest match to the desired integer.


I have records that have fixed values in the respective field containing the following values;
2
4
8
12
16
If the desired integer is 75; I would require the returned result as follows;
4 x 16
1 x 12
(remainder 1)
The match must return a value that is equal to or larger than the desired integer.
This must resolve with the fewest multiple of records as possible, i.e. it could not resolve as 18 x 4


To add further complexity to the problem, I need to be able to add weighted favour in bias of using fewer multiples. I would say the acceptable bias would be in favour of having a remainder of 3 over using an additional record to achieve the exact integer.
Example:
If the desired integer is 38; I would require the returned result as follows;
2 x 16
1 x 8
(remainder 2)
Rather than
2 x 16
1 x 4
1 x 2
(exact match)

At present I just have a fixed matrix with all combinations from 1-94. But this is not at all scalable.
 

Minty

AWF VIP
Local time
Today, 03:20
Joined
Jul 26, 2013
Messages
7,484
This sounds like it could be an Assignment?

I think it's a job for an array and a couple of loops.
What have you tried so far apart from your matrix?
 

Hasslehump

New member
Local time
Today, 03:20
Joined
May 16, 2020
Messages
4
Only a personal assignment! I'm not in any form of study at present. I'm essentially trying to create an auto-calculator for a parts list.

I haven't tried anything other than searching the web so far, I'm completely stuck on idea's for this. I'm wondering if perhaps I'm out of my depth on this if I'm honest.

I haven't used an array in Access before, I'll look in to this now.

Thanks
 

Minty

AWF VIP
Local time
Today, 03:20
Joined
Jul 26, 2013
Messages
7,484
It's certainly not a simple one to solve, but you would need to keep storing the results and comparing to the next calculation.
This is sometimes referred to as the Bin Packing Problem or at least it is pretty similar, this might get you started - it's for excel, but still VBA
 

Hasslehump

New member
Local time
Today, 03:20
Joined
May 16, 2020
Messages
4
That's great thank you!

I did first create this in Excel so I can try to solve in that first then make it work in Access afterwards.

I'll update if I solve this.
 

Hasslehump

New member
Local time
Today, 03:20
Joined
May 16, 2020
Messages
4
Update:

I think I'm nearly there but really struggling with the VBA code.

Side note: I haven't done any coding since Hello World over 10 years ago so might be missing something very basic here, and apologies for any crappy formatting!

It seems to me, the issue is that the "total" isn't being updated after each If statement is completed and the "quantity" is multiplied, therefore each switch is being treated individually so the output is ridiculous.

Thanks in advance for any help on the below;

Code:
Option Explicit

Private Sub CommandButton1_Click()

Dim limit As Double, value As Double, totalWeight As Double, total As Double
Dim switcha As Double, switchb As Double, switchc As Double, switchd As Double, switche As Double
Dim quantitya As Double, quantityb As Double, quantityc As Double, quantityd As Double, quantitye As Double

limit = Range("D5").value
total = ((Range("F2").value * Range("F3").value) + (Range("E2").value * Range("E3").value) + (Range("D2").value * Range("D3").value) + (Range("C2").value * Range("C3").value) + (Range("B2").value * Range("B3").value))
switcha = Range("B2").value
switchb = Range("C2").value
switchc = Range("D2").value
switchd = Range("E2").value
switche = Range("F2").value
quantitya = Range("B3").value
quantityb = Range("C3").value
quantityc = Range("D3").value
quantityd = Range("E3").value
quantitye = Range("F3").value

Range("B5").value = total
  

If total <= limit Then
    Range("F3") = Application.WorksheetFunction.RoundDown((limit + 3) / switche, 0)
End If
Range("B5").value = total
If total <= limit Then
    Range("E3") = Application.WorksheetFunction.RoundDown((limit + 3) / switchd, 0)
End If
Range("B5").value = total
If total <= limit Then
    Range("D3") = Application.WorksheetFunction.RoundDown((limit + 3) / switchc, 0)
End If
Range("B5").value = total
If total <= limit Then
    Range("C3") = Application.WorksheetFunction.RoundDown(limit / switchb, 0)
End If
Range("B5").value = total
If total <= limit Then
    Range("B3") = Application.WorksheetFunction.RoundDown(limit / switcha, 0)
End If


Range("B5").value = total

End Sub

1589706681044.png
 

Gasman

Enthusiastic Amateur
Local time
Today, 03:20
Joined
Sep 21, 2011
Messages
7,109
I am not going to make any pretence at understanding how you are going to do it, but hoping if I point out a few things, that might help you see where you have gone wrong.?

You set Range("B5").value = total multiple times, but total never changes.?
You test If total <= limit also multiple times yet limit never changes.?

HTH
 

MajP

You've got your good things, and you've got mine.
Local time
Yesterday, 22:20
Joined
May 21, 2018
Messages
3,595
I will take a look at this, I have a reputation on this site for solving the hard optimization and math problems. I have demonstrated dijkstras algorithm, knap-sack, bin-pack, assignment models. Etc That bin packing may not work, because it cannot ensure an integral solution, but you did make it easy with all multiples of 2. You are dealing with an Integer Factorization problem for which there are algorithms to do this. Some here:
Here is a more robust example of a binpack with 1000s of records. You may find this interesting.
 

MajP

You've got your good things, and you've got mine.
Local time
Yesterday, 22:20
Joined
May 21, 2018
Messages
3,595
I do not understand the logic or how this would be applied. If the number is 38 then
2X16 1X8 equals 40 and that is not a remainder that is an excess. If that is better, why not 3X16 (48) with a remainder of 10. What is the real rule?
To add further complexity to the problem, I need to be able to add weighted favour in bias of using fewer multiples. I would say the acceptable bias would be in favour of having a remainder of 3 over using an additional record to achieve the exact integer.
Example:
If the desired integer is 38; I would require the returned result as follows;
2 x 16
1 x 8
(remainder 2)
Rather than
2 x 16
1 x 4
1 x 2
(exact match)
 

arnelgp

error reading drive A:
Local time
Today, 11:20
Joined
May 7, 2009
Messages
10,829
im not sure if this is correct?
 

Attachments

  • combiNaNa.zip
    35 KB · Views: 11

MajP

You've got your good things, and you've got mine.
Local time
Yesterday, 22:20
Joined
May 21, 2018
Messages
3,595
Your problem is easy except for the addition of the number 12. This now becomes a traditional optimization problem where you cannot simply look forward to the next case, you have to look beyond it for a better solution. If it was 16, 8, 4, 2 then the problem is easy it could be done serial. You divide by the largest in a serial fashion. But since 16 is not a factor of 12 and 12 is not a factor of 8 then you cannot come up with a simple serial solution. Good example in this case is 36. The solution is 3 x 12, but if you did this in a serial fashion then you would get
16 x 2
1 x 4

So ArnelGP code fails for this case. I did not look at the code, but It actually gave the answer:
4*8
1*4

I have not played with it, but as long as your divisors do not change, you probably need to divide by 12 first and see what is leftover. If is 0 to 3 then that is your best answer. If the remainder is 4 or more, I think you can start in a serial fashion.

Note: I am assuming that it is the count of divisors matters as well as the number of divisors. In other words use the bigger values first. So if the number is 35
16 x 2
1 x 2
R x 1
(count 4 r1)

is better than
8 x 4
2 x 1
R x 1
(count 5 r1)

If that is not the case then again it makes no sense. Just divide everything by 2.
 

The_Doc_Man

Immoderate Moderator, Former MVP, Retired SysAdmin
Staff member
Local time
Yesterday, 21:20
Joined
Feb 28, 2001
Messages
18,302
Were it not for the "12" in the list I would say do some binary masking because with 16, 8, 4, and 2 you have trivial cases. But looking at the Excel spreadsheet, I suddenly smell something else here. The requirement to minimize the number of "tuples" (n x m) and the fact that 12 is one of the possible tuple members make me think that this problem is similar to an attempt to find the optimum purchase of some kind of adapter or router. Tell us the actual goal, not in numbers or formulas or code, but as a problem description of minimizing a purchase - and the parameters of the purchase.
 

MajP

You've got your good things, and you've got mine.
Local time
Yesterday, 22:20
Joined
May 21, 2018
Messages
3,595
I reread this a couple of times and I think I got your requirement.
1) You can get an exact factorization or be over
2) You can be over if it is less than the bias

Code:
Public Type Divisors
  NumberOf16s As Integer
  NumberOf12s As Integer
  Numberof8s As Integer
  NumberOf4s As Integer
  NumberOf2s As Integer
  Overage As Integer
End Type

Public Function GetFactorization(ByVal TheNumber As Double, Optional Bias As Integer = 3) As Divisors
  'if the overage is less than the bias add another factor
  Dim TheDivisors As Divisors
  If TheNumber >= 16 Then
    TheDivisors.NumberOf16s = (TheNumber \ 16)
    TheNumber = TheNumber - (16 * TheDivisors.NumberOf16s)
    If 16 - TheNumber < Bias Then
      TheDivisors.Overage = 16 - TheNumber
      TheDivisors.NumberOf16s = TheDivisors.NumberOf16s + 1
      GetFactorization = TheDivisors
      Exit Function
    End If
  End If
  If TheNumber >= 12 Then
    TheDivisors.NumberOf12s = (TheNumber \ 12)
    TheNumber = TheNumber - (12 * TheDivisors.NumberOf12s)
    If 12 - TheNumber < Bias Then
      TheDivisors.Overage = 12 - TheNumber
      TheDivisors.NumberOf12s = TheDivisors.NumberOf12s + 1
      GetFactorization = TheDivisors
      Exit Function
    End If
  End If
  If TheNumber >= 8 Then
    TheDivisors.Numberof8s = (TheNumber \ 8)
    TheNumber = TheNumber - (8 * TheDivisors.Numberof8s)
    If 8 - TheNumber < Bias Then
      TheDivisors.Overage = 8 - TheNumber
      TheDivisors.Numberof8s = TheDivisors.Numberof8s + 1
      GetFactorization = TheDivisors
      Exit Function
    End If
  End If
  If TheNumber >= 4 Then
    TheDivisors.NumberOf4s = (TheNumber \ 4)
    TheNumber = TheNumber - (4 * TheDivisors.NumberOf4s)
    If 4 - TheNumber < Bias Then
      TheDivisors.Overage = 4 - TheNumber
      TheDivisors.NumberOf4s = TheDivisors.NumberOf4s + 1
      GetFactorization = TheDivisors
      Exit Function
    End If
  End If
  If TheNumber >= 2 Then
    TheDivisors.NumberOf2s = (TheNumber \ 2)
    TheNumber = TheNumber - (2 * TheDivisors.NumberOf2s)
    Debug.Print "at 2 the number " & TheNumber
    If TheNumber > 0 Then
      TheDivisors.Overage = 2 - TheNumber
      TheDivisors.NumberOf2s = TheDivisors.NumberOf2s + 1
      GetFactorization = TheDivisors
    End If
  End If
  If TheNumber > 0 Then
    TheDivisors.Overage = 2 - TheNumber
    TheDivisors.NumberOf2s = TheDivisors.NumberOf2s + 1
    GetFactorization = TheDivisors
  End If
  GetFactorization = TheDivisors
End Function

So I think based on your definition this can be done serially. If it is true by your rules that for the number 72
4 X 16
1 x 8
is better than
6 x 12

In the second one you have only one case but 5 is less than 6. I originally thought you wanted to minimize the cases and not the sum of the multipliers.

So basically the logic is
Divide by 16. If 16 - remainder < bias, then add another 16. Example
79.
79 / 16 = 4 R 15
16-15 = 1 which is less than the bias so
add another group of 16 and the answer is
5 X 16 with overage of 1

Keep doing the same logic as you go downwards.

I think I captured your logic but it is a little strange. Not sure what you are final purpose is. So for the number 6 this gives
2x4
overage of 2 (since 2 is less than the bias of 3)
vs
1x4
1X2
 

Attachments

  • FindFactorization.accdb
    436 KB · Views: 9
Last edited:

arnelgp

error reading drive A:
Local time
Today, 11:20
Joined
May 7, 2009
Messages
10,829
Updated with "Bias"
 

Attachments

  • combiNaNa.zip
    108 KB · Views: 9

MajP

You've got your good things, and you've got mine.
Local time
Yesterday, 22:20
Joined
May 21, 2018
Messages
3,595
@Hasslehump
You will need to look at both to see what meets your interpretation. Or if neither does. We took different interpretations. Arnelgp is looking at the bias before and I am after. Sometimes my answer is better sometimes his is. My guess is that you want to minimize the overage as well as the number of multipliers.

For 2
Arnelgp: 1x4 with overage of 2
Me: 1X2 (better)

For 5
Anrelgp: 1x8 with overage of 3
me: 2x4 with overage of 3 (same)

For 7
Anrelgp: 1x8, 1x2. with overage of 3 (that appears to be a bug should be just 1x8 with overage of 1, same problem with 8)
me: 2x4 with overage of 1 (better)

For 10
Arnelgp: 1x12 overage of 2 (better same for 11 and 13)
Me: 1x8, 1x2

For 17
Arnelgp: 1x16, 1x4 overage 3
me: 1x16, 1x2 overage of 1 (Better smaller overage)

For 18
Arnelgp: 1x16, 1x4, overage of 2
Me: 1x16, 1x2 (better no overage)

One solution could be to combine both of these methods of before and after. So for 18. If both solutions have the same multipliers (1 and 1) then pick the one with the smallest overage. Or for 10,11,13 take the solution with wth smallest sum of multipliers.
 

Users who are viewing this thread

Top Bottom