VBA - Backpack problem

Asked

Viewed 1,225 times

7

In excel I have the following table

| Produtos  | Preço |
| Produto A | 100   |
| Produto B | 250   |
| Produto C | 200   |
| Produto D | 800   |
| Produto E | 560   |
| Produto F | 970   |
...

And I would like to make all possible combinations through the price

Exemplo preço: 1000

Upshot

Produto A x10
Produto B x4
Produto A x5 Produto B x2
Produto D x1 Produto C x1
...

The total number of combinations must be equal for the informed price, and may have several different combinations of N products for N products. My biggest doubt is how to create an algorithm like this? I tried to run a for all products, but I believe this is not the best way

For i = 1 To linha 'total de produtos'
    linhaId = CInt(Plan1.Cells(i + 1, 4)) 

    If (linhaId > 0) Then
        preco = CInt(Plan1.Cells(linhaId, 2))
        If ((soma + preco) <= CInt(limiteTotalPreco)) Then
            soma = soma + preco
        Else
            Plan2.Cells(newlinha, 1) = soma
            newlinha = newlinha + 1

            soma = preco
        End If
    End If
Next

The problem is that the combination is not done, and I can’t find a solution to run this information loop

vba excel

  • What do you mean when you say "And I would like to make all possible combinations through price"? I can’t understand what you’re trying to do

  • 1

    Now I get it ... you want to quote a price, and see what are the combinations of each product (and even several different products) that equal that price... right?

  • Where you’re keeping the combinations?

  • @Mattjohnson This same, and can also be the same product 2x or 3x combined with other products

  • You first need to find the algorithm that does what you need, even if it is pseudo-algorithm. Then ask the question.

  • The original backpack problem involves finding an optimal solution (http://pt.wikipedia.org/wiki/Problema_da_backpack: "Metaphorically we can understand it as the challenge of filling a backpack without exceeding a certain weight limit, optimizing the value of the loaded product."). However, you want to produce all possible combinations. Note that if you test only the combinations between different products (ignoring combinations additional of the same product 2x, 3x, ..., etc.), the problem would already have exponential complexity. You have some specific intention with this algorithm?

  • @Luizvieira I thought about the "backpack problem", because I thought it could be the solution to build my algorithm, by the question "fill the backpack without exceeding a determining weight limit"in my case I want to fill a cart with N products and combinations defined by the limit of the Value

  • @Makah initially the algorithm I found is this "backpack problem" the big problem I’m not so sure if it will be fully useful...

Show 3 more comments

1 answer

7


As I mentioned in the comment, your problem is not exactly the backpack problem classic, because you’re not looking for an optimal solution (like the minimum number of shopping carts to accommodate all products, for example). Still you are right in the fact that your problem remembers the problems of combinatorial optimization.

I made a rather "innocent" attempt (in the sense that I didn’t care about the performance of the algorithm) with the hope that I could help you. Thanks as a cool exercise to remind me how VBA works. :)

The principle of the solution I am proposing is the following:

  • As with the greedy approach to solving the classic backpack problem, items are ordered in descending order of price. This helps in the sense that the most expensive items are eliminated quickly (in your example you can notice that product F, which costs 950) does not "fit" in cart 1000 max with no other product).

  • As you would like to have the various combinations of each product (X1, x2, X3, ..., etc.), it is necessary to calculate what is the maximum of items of a product that would fit in the cart. You will notice in the algorithm that there is a loop (For iQtd = 1 To iQtdMax) just to treat these combinations.

  • The implementation is inherently recursive (and here is my concern about complexity - more about the end), so for each quantity of a product the algorithm searches for all possible combinations of the following products that fit in the remaining price (recalling that the algorithm is based on the fact that the list of products is ordered from the highest to the lowest price). For example, when the algorithm is treating product B (which can be placed in the trolley at most 1000 / 250 = 4 times), it will make the combinations for the amounts of B from 1 to 4. Assuming it is in the loop where the amount iQtd is equal to 3. This means that in the cart there will be the equivalent of 3 x 250 = 750, and so only 150 will remain to try to include the next items of lesser value (i.e., products C and A). Note that the value of this difference is passed in the function’s recursive call Combine.

  • The function Combine treats the elements directly using the object Worksheet.Range from VBA, but you can change this to an array if you prefer. Also, your return is a string array with the combinations in the same way that you used in your question, merely as an illustration. You can modify to return the way you think most appropriate.

Here’s the code I built for example.

Option Base 1

' Macro chamada pelo botão na planilha "Dados".
' Apenas faz a mágica e cria uma nova planilha "Resultado" com as combinações.
Sub GenerateList()

On Error Resume Next

    Dim dMaxPrice As Double
    Dim oData As Range
    Dim aResp() As String
    Dim oSheet As Worksheet

    ' Ordena os dados em ordem descendente de preço
    Set oData = Range("A2:B7")
    oData.Sort key1:=Range("B2:B7"), Order1:=xlDescending

    ' Obtém o preço máximo
    dMaxPrice = CDbl(Cells(1, 5).Value)

    ' Monta a lista de combinações com os dados
    aResp = Combine(oData, dMaxPrice)

    Set oSheet = Worksheets("Resultado")
    If Err = 0 Then
        Application.DisplayAlerts = False
        oSheet.Delete
        Application.DisplayAlerts = True
    End If

    Set oSheet = ActiveWorkbook.Worksheets.Add(After:=Worksheets("Dados"))
    oSheet.Name = "Resultado"
    For i = 1 To UBound(aResp)
        oSheet.Cells(i, 1).Value = aResp(i)
    Next i
    oSheet.Columns(1).AutoFit
    oSheet.Activate

End Sub

' Esta é a função que propriamente faz as combinações
' Ela está meramente recursiva, então note que sua complexidade é exponencial com relação
' à quantidade de dados de entrada.
'
' Parâmetros:
' oData Objeto Worksheet.Range com os dados processados em cada chamada recursiva.
' dMaxPrice Valor (double) com o limite de preço restante no nível da chamada.
'
' Retorno:
' Retorna um array de strings com as combinações no formato "Produto A x? Produto B x? ..."
' como no exemplo da sua questão.
Function Combine(ByVal oData As Range, ByVal dMaxPrice) As Variant

On Error Resume Next

    Dim sProduct As String
    Dim dPrice As Double
    Dim iQtdMax As Integer
    Dim sRangeDef As String
    Dim oSubData As Range
    Dim aRet() As String
    Dim aCombReports() As String
    Dim iSize As Integer

    For iProd = 1 To oData.Rows.Count

        ' Nome e preço do produto atual
        sProduct = oData.Cells(iProd, 1)
        dPrice = oData.Cells(iProd, 2)

        ' Quantidade máxima de itens do produto atual, segundo seu preço e o limite máximo
        iQtdMax = Int(dMaxPrice / dPrice)

        ' Demais produtos no intervalo de dados além do produto atual
        If (iProd + 1 <= oData.Rows.Count) Then
            sRangeDef = "A" + CStr(iProd + 1) + ":B" + CStr(oData.Rows.Count)
            Set oSubData = oData.Range(sRangeDef)
        Else
            Set oSubData = Nothing
        End If

        ' Calcula todas as combinações de quantidades do produto atual,
        ' recursivamente incluindo as combinações dos demais produtos DE
        ' MENOR VALOR (devido ao fato do intervalo original de dados estar
        ' ordenado por preço em ordem descrescente)
        For iQtd = 1 To iQtdMax

            sReport = sProduct + " x" + CStr(iQtd) + " "
            dPriceRest = dMaxPrice - (iQtd * dPrice)

            ' Chamada recursiva indicando o preço máximo descontado o total de itens do produto inicial incluídos
            ' (Se, é claro, há preço sobrando para incluir mais produtos).
            If dPriceRest > 0 And Not oSubData Is Nothing Then
                aCombReports = Combine(oSubData, dPriceRest)
            Else
                Erase aCombReports
            End If

            ' Monta o retorno com as combinações obtidas para os demais produtos
            Err = 0
            iCombs = UBound(aCombReports)
            If Err = 0 Then
                Err = 0
                For Each sCombRep In aCombReports
                    Err = 0 ' <-------- LINHA ADICIONADA NA EDIÇÃO
                    iSize = UBound(aRet)
                    If Err <> 0 Then iSize = 0
                    ReDim Preserve aRet(iSize + 1)
                    aRet(iSize + 1) = sReport + sCombRep
                Next

            ' Se não retornou combinações, monta o retorno apenas com o produto atual
            Else
                Err = 0
                iSize = UBound(aRet)
                If Err <> 0 Then iSize = 0
                ReDim Preserve aRet(iSize + 1)
                aRet(iSize + 1) = sReport
            End If

        Next iQtd

    Next iProd

    ' Devolve o array de combinações
    Combine = aRet

End Function

Important remarks:

  1. Like I said, it’s not exactly the backpack problem, although it’s a combinatorial problem.
  2. The implementation I’m suggesting is innocent good and has no concern for performance. Note that the algorithm is recursive and therefore its complexity is exponential in relation to the size of the input data. In your example it worked very well, but for a large amount of data (quantity of products) can become unviable.
  3. It may be possible to use dynamic programming to decrease the cost of recursion. But honestly, I didn’t think about it and leave this homework to you (or someone else’s answer).

The result that this code produces is this (total of 72 combinations):

Produto F x1 
Produto D x1 Produto C x1 
Produto D x1 Produto A x1 
Produto D x1 Produto A x2 
Produto E x1 Produto B x1 Produto A x1 
Produto E x1 Produto C x1 Produto A x1 
Produto E x1 Produto C x1 Produto A x2 
Produto E x1 Produto C x2 
Produto E x1 Produto A x1 
Produto E x1 Produto A x2 
Produto E x1 Produto A x3 
Produto E x1 Produto A x4 
Produto B x1 Produto C x1 Produto A x1 
Produto B x1 Produto C x1 Produto A x2 
Produto B x1 Produto C x1 Produto A x3 
Produto B x1 Produto C x1 Produto A x4 
Produto B x1 Produto C x1 Produto A x5 
Produto B x1 Produto C x2 Produto A x1 
Produto B x1 Produto C x2 Produto A x2 
Produto B x1 Produto C x2 Produto A x3 
Produto B x1 Produto C x3 Produto A x1 
Produto B x1 Produto A x1 
Produto B x1 Produto A x2 
Produto B x1 Produto A x3 
Produto B x1 Produto A x4 
Produto B x1 Produto A x5 
Produto B x1 Produto A x6 
Produto B x1 Produto A x7 
Produto B x2 Produto C x1 Produto A x1 
Produto B x2 Produto C x1 Produto A x2 
Produto B x2 Produto C x1 Produto A x3 
Produto B x2 Produto C x2 Produto A x1 
Produto B x2 Produto A x1 
Produto B x2 Produto A x2 
Produto B x2 Produto A x3 
Produto B x2 Produto A x4 
Produto B x2 Produto A x5 
Produto B x3 Produto C x1 
Produto B x3 Produto A x1 
Produto B x3 Produto A x2 
Produto B x4 
Produto C x1 Produto A x1 
Produto C x1 Produto A x2 
Produto C x1 Produto A x3 
Produto C x1 Produto A x4 
Produto C x1 Produto A x5 
Produto C x1 Produto A x6 
Produto C x1 Produto A x7 
Produto C x1 Produto A x8 
Produto C x2 Produto A x1 
Produto C x2 Produto A x2 
Produto C x2 Produto A x3 
Produto C x2 Produto A x4 
Produto C x2 Produto A x5 
Produto C x2 Produto A x6 
Produto C x3 Produto A x1 
Produto C x3 Produto A x2 
Produto C x3 Produto A x3 
Produto C x3 Produto A x4 
Produto C x4 Produto A x1 
Produto C x4 Produto A x2 
Produto C x5 
Produto A x1 
Produto A x2 
Produto A x3 
Produto A x4 
Produto A x5 
Produto A x6 
Produto A x7 
Produto A x8 
Produto A x9 
Produto A x10
  • 1

    Sincerely Luiz very show your answer dear, I will analyze here all the items, thank you very much!

  • Luiz worked perfectly, but only has a part of the code that I did not understand very well, if I put the value Maximum price: 1800, brings the result "Product F X1 Product A X8" and this is the only combination of "Product F", and could also have "Product F X1 Product C X4". This only happens with the highest value product, this happens due to the fact that you mentioned above "The implementation is inherently recursive..."

  • @Tiago In fact there was an error, but it has nothing to do with recursion. I forgot to reset the error variable used to check if the return matrix was empty. I fixed and marked it with a comment in the code.

  • Good afternoon. It would be possible to re-upload this spreadsheet. I have exactly the same need exposed here.

  • Hello @Andersongomes. I don’t know why, but the spreadsheet was deleted in my 4shared account. I already checked in his Recycle Bin and it’s not there. I also didn’t keep it on my computer because it’s a very simple example. So unfortunately I don’t have it anymore. But it’s really simple, it only had the product data (from A to F) just like the AP puts the question, and a button that ran the macro with the code (which you can copy from the answer)

Browser other questions tagged vba excel

You are not signed in. Login or sign up in order to post.