Como eu mencionei no comentário, o seu problema não é exatamente o problema da mochila clássico, porque você não está buscando encontrar uma solução ótima (como o número mínimo de carrinhos de compra para acomodar todos os produtos, por exemplo). Ainda assim você tem razão no fato de que o seu problema lembra os problemas de otimização combinatória.
Eu fiz uma tentativa bastante "inocente" (no sentido de que não me preocupei com o desempenho do algoritmo) com a esperança de que possa lhe ajudar. Valeu como um exercício bacana pra eu lembrar como funciona o VBA. :)
O princípio da solução que eu estou propondo é o seguinte:
Assim como na abordagem gulosa de resolução do problema da mochila clássico, os itens são ordenados em ordem decrescente de preço. Isso ajuda no sentido de que os itens mais caros são eliminados rapidamente (no seu exemplo dá pra notar que o produto F, que custa 950) não "cabe" no carrinho de máximo 1000 com nenhum outro produto).
Como você gostaria de ter as diversas combinações de cada produto (x1, x2, x3, ..., etc), é necessário calcular qual é o máximo de itens de um produto que caberia no carrinho. Você notará no algoritmo que existe um laço (For iQtd = 1 To iQtdMax
) justamente pra tratar essas combinações.
A implementação é inerentemente recursiva (e aqui está a minha preocupação com relação a complexidade - mais a respeito no final), de forma que para cada quantidade de um produto o algoritmo busca todas as possíveis combinações dos produtos seguintes que cabem no preço restante (lembrando que o algoritmo se baseia no fato de que a lista de produtos está ordenada do maior para o menor preço). Por exemplo, quando o algoritmo estiver tratando o produto B (que pode ser colocado no carrinho no máximo 1000 / 250 = 4
vezes), ele irá fazer as combinações para as quantidades de B de 1 a 4. Supondo que se está no laço em que a quantidade iQtd é igual a 3. Isso significa que no carrinho haverá o equivalente a 3 x 250 = 750
, e por isso restará apenas 150 para tentar incluir os próximos itens de valor menor (isto é, os produtos C e A). Note que o valor dessa diferença é passado na chamada recursiva da função Combine
.
A função Combine
trata os elementos utilizando diretamente o objeto Worksheet.Range
do VBA, mas você pode trocar isso para uma matriz se preferir. Além disso, o seu retorno é uma matriz de strings com as combinações da mesma forma que você usou na sua questão, meramente como forma de ilustração. Você pode modificar pra devolver da maneira que achar mais apropriado.
Eis aqui o código que eu construi de exemplo.
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
Observações importantes:
- Como eu disse, não se trata exatamente do problema da mochila, embora seja um problema de combinatória.
- A implementação que eu estou sugerindo é bem inocente e não tem qualquer preocupação com desempenho. Note que o algoritmo é recursivo e por isso sua complexidade é exponencial em relação ao tamanho dos dados de entrada. No seu exemplo funcionou muito bem, mas para um volume de dados (quantidade de produtos) grande pode ficar inviável.
- Talvez seja possível utilizar programação dinâmica para diminuir o custo da recursão. Mas, honestamente, não cheguei a pensar a respeito e deixo essa lição de casa pra você (ou pra resposta de outra pessoa).
O resultado que esse código produz é esse (total de 72 combinações):
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