Estou procurando encontrar uma solução para o seguinte problema, mas estou tendo problemas para formulá-la com sensibilidade e, em seguida, encontrando um algoritmo apropriado para resolvê-lo.
Considere uma lista de itens colocados em uma sacola de compras: 1, 2, 3, 4 ...
Cada item pode fazer parte de uma ou mais promoções: A, B, C, D
Desejamos aplicar o conjunto de promoções de modo a maximizar o valor do desconto, para que nenhum item possa participar de mais de uma promoção, mas cada promoção pode ser aplicada mais de uma vez.
As promoções podem ser definidas de várias maneiras, mas, por enquanto, estou apenas pensando em um tipo de 'Compre 2 itens qualificados, salve X', espero que eu possa generalizar a partir daqui.
Meu exemplo seria:
- Promoção A - Compre 2 Economize 8
- Promoção B - Compre 2 Economize 10
Promoção C - Compre 2 Economize 6
Item 1 - Elegível para A, B
- Item 2 - Elegível para B
- Item 3 - Elegível para A, C
- Item 4 - Elegível para B, C
É fácil ver aqui que a aplicação correta das promoções é de A ao Item 1, 3 e B a 2, 4. Isso dá um desconto total de 18.
Em um caso maior, torna-se difícil, portanto, é necessário resolver algoritmicamente.
Eu tentei o seguinte:
- Liste todas as combinações possíveis de promoções que poderíamos aplicar.
- Descarte qualquer um que seja obviamente ruim (por exemplo, uma cópia direta de uma promoção com um valor mais alto).
- Aplique qualquer que não se sobreponha a outras promoções (por exemplo, se os itens 1 e 2 são válidos apenas para a promoção A, aplique essa promoção).
- Pegue o conjunto restante e tente uma pesquisa do tipo branch-and-bound nos resultados.
No entanto, isso pode levar muito tempo (para conjuntos grandes com descontos semelhantes).
Sinto que esse é um tipo de problema de mochila ou atribuição, mas não posso escrevê-lo com sensibilidade. Sem poder escrever com sensatez, não consigo resolvê-lo.
Essa é uma variante reconhecida de um problema? Qualquer ajuda para atacá-lo seria muito apreciada, especialmente com o código psuedo para ajudar a resolvê-lo
fonte
Respostas:
Parece que você gostaria de aproveitar a estrutura do problema, pois os itens só podem ser usados para uma promoção. Isso significa que, se você encontrou uma solução que usa o maior número possível de promoções, a única maneira de melhorar é encontrar outra solução que use uma ou mais promoções, além dos itens não atribuídos, e troque-as por outro conjunto de promoções e itens não utilizados de maior valor.
Por exemplo, você pode iniciar o exemplo anterior com (1,2) e (3,4), para 16. Você pode verificar se (1,3) e (2,4) levam a 18, e a troca deve ser fez.
fonte