Venda de Bob (reordenação de pares com restrições para minimizar a soma de produtos)

Eu fiz essa pergunta no Stack Overflow há um tempo atrás: Problema: a venda de Bob . Alguém sugeriu postar a pergunta aqui também.

Alguém já fez uma pergunta relacionada a esse problema aqui - subfloresta de peso mínimo de determinada cardinalidade - mas, pelo que entendi, não me ajuda com o meu problema. A resposta mais bem avaliada no StackOverflow também vale a pena olhar.

Aqui está a cópia literal da minha pergunta StackOverflow. Provavelmente, ele foi formulado de forma inadequada para este site (caramba, me sinto inadequadamente sem instrução apenas pedindo aqui), portanto, fique à vontade para editá-lo:

Nota: esta é uma reformulação abstrata de um problema da vida real em relação à solicitação de registros em um arquivo SWF. Uma solução me ajudará a melhorar um aplicativo de código aberto.

Bob tem uma loja e quer fazer uma venda. Sua loja possui vários produtos e ele possui uma certa quantidade inteira de unidades de cada produto em estoque. Ele também possui várias etiquetas de preço montadas em prateleiras (até o número de produtos), com os preços já impressos. Ele pode colocar qualquer etiqueta de preço em qualquer produto (preço unitário de um item para todo o estoque desse produto), no entanto, alguns produtos têm uma restrição adicional - esse produto pode não ser mais barato que um determinado produto.

Você deve descobrir como organizar as etiquetas de preço, de modo que o custo total de todos os produtos de Bob seja o mais baixo possível. O custo total é a soma da etiqueta de preço atribuída a cada produto multiplicada pela quantidade desse produto em estoque.

Dado:

• N - o número de produtos e etiquetas de preços
• S _i , 0≤ i <N - a quantidade em estoque do produto com o índice i (número inteiro)
• P _j , 0≤ j <N - o preço na etiqueta de preço com o índice j (número inteiro)
• K - o número de pares de restrições adicionais
• A _k , B _k , 0≤ k <K - índices de produto para a restrição adicional
  • Qualquer índice de produto pode aparecer no máximo uma vez em B. Portanto, o gráfico formado por esta lista de adjacências é na verdade um conjunto de árvores direcionadas.

O programa deve encontrar:

• M _i , 0≤ i <N - mapeamento do índice do produto para o índice da etiqueta de preço (P _{M i} é o preço do produto i )

Para satisfazer as condições:

1. P _{M A k} ≤ P _{M B k} , para 0≤ k <K
2. Σ (S _i × P _{M i} ) para 0≤ i <N é mínimo

Observe que, se não fosse a primeira condição, a solução seria simplesmente classificar rótulos por preço e produtos por quantidade e combinar ambos diretamente.

Os valores típicos para entrada serão N, K <10000. No problema da vida real, existem apenas várias etiquetas de preço distintas (1,2,3,4).

Aqui está um exemplo de por que a maioria das soluções simples (incluindo classificação topológica) não funciona:

$\$$$\$$

A solução ideal é:

Price, $   1  2  3  4  5  6  7  8  9 10
Qty        9  8  7  6  1 10  5  4  3  2

$\$$

Também postei isso na sua pergunta original no Stack Overflow:

O problema é NP-completo para o caso geral. Isso pode ser demonstrado através de uma redução de 3 partições (que ainda é uma versão NP completa e forte da embalagem do compartimento).

Seja w ₁ , ..., w _n o peso dos objetos da instância de 3 partições, b seja o tamanho do compartimento e k = n / 3 o número de compartimentos que podem ser preenchidos. Portanto, há uma partição 3 se os objetos puderem ser particionados de modo que haja exatamente 3 objetos por compartimento.

Para a redução, definimos N = kb e cada compartimento é representado por b etiquetas de preço do mesmo preço (pense em P _i aumentando cada b- ésima etiqueta). Vamos t _i , 1≤ i ≤ k , ser o preço das etiquetas correspondente ao i th bin. Para cada w _i , temos um produto S _j de quantidade w _i + 1 (vamos chamá-lo de produto raiz de w _i ) e outros w _i - 1 produtos de quantidade 1, que devem ser mais baratos que S _j (chame esses produtos de licença).

Para t _i = (2b + 1) ⁱ , 1≤ i ≤ k , há uma partição _tripla se e somente se Bob puder vender por 2b Σ _{1≤ i ≤ k} t _i :

• Se houver uma solução para três partições, todos os produtos b correspondentes aos objetos w _i , w _j , w _l atribuídos à mesma bandeja podem ser rotulados com o mesmo preço sem violar as restrições. Assim, a solução custou 2b Σ _{1≤ i ≤ k} t _i (uma vez que a quantidade total de produtos com preço t _i é 2b ).
  
• Considere uma solução ideal para a venda de Bob. Primeiro, observe que, em qualquer solução, mais de três produtos raiz compartilham o mesmo preço; para cada produto raiz que é "demais", existe um preço mais barato que fica em menos de três produtos raiz. Isso é pior do que qualquer solução: existem exatamente 3 produtos raiz por etiqueta de preço (se existir).
  Agora ainda pode haver uma solução de Bob's Sale com três rótulos-raiz por preço, mas seus produtos de licença não usam os mesmos rótulos de preço (os depósitos meio que fluem). Digamos que as etiquetas de preço mais caras sejam um produto raiz de w _i que tenha um produto com licença mais barato. Isso implica que os três rótulos raiz w _i , w _j , w _lmarcados com o preço mais caro não somam b . Portanto, o custo total dos produtos marcados com esse preço é de pelo menos 2b + 1 .
  Portanto, essa solução custou t _k (2b + 1) + algum outro custo de atribuição. Como o custo ideal para uma partição _{tridimensional} existente é 2b Σ _{1≤ i ≤ k} t _i , temos que mostrar que o caso considerado é pior. Este é o caso se t _k > 2b Σ _{1≤ i ≤ k-1} t _i (observe que é k-1 na soma agora). Configurando t _i= (2b + 1) ⁱ , 1≤ i ≤ k , este é o caso. Isso também vale, se não o preço mais caro, é o "ruim", mas qualquer outro.

Portanto, esta é a parte destrutiva ;-) No entanto, se o número de diferentes preços for constante, você poderá usar a programação dinâmica para resolvê-lo em tempo polinomial.

Este é um acompanhamento da resposta de Gero . A idéia é modificar sua construção para mostrar uma forte dureza NP.

$t_i=(2b+1)^i$$t_i=i$$P=2b\sum_{1\leq i \leq k} t_i$

$w_i-1$$P$$P$

Portanto, só é possível obter o prêmio reivindicado, se todos os produtos em folha tiverem o mesmo prêmio que seu produto-raiz, o que significa que existe uma partição em 3 partes.

$k$$f(k)\cdot n^{O(1)}$$n^{O(k)}$

Também postado na pergunta original sobre estouro de pilha.

Isso soa como uma questão da teoria dos jogos. Nesse caso, uma solução muito simples de força bruta é:

Vamos assumir que as restrições representam alguns invariantes da forma

S-> AkSBk | AkBkS | SAkBk

A solução é continuar adicionando primeiro as restrições e depois os elementos. Ex .: Digamos que n = 10 e existem 2 restrições, A1B1 e A2B2. Depois, há três filhos no nó raiz (nível 2). Cada um desses 3 nós terá 7 filhos no nível 3, cada um dos 21 no 6, no nível 4, etc. Essencialmente, você está executando todas as combinações possíveis.

                A1B1 --- Nível 1 
               / | \
              / | \
             / | \
            / | \
    A1A2B2A1 A1B1A2B2 A2B2A1B1 --- Nível 2

e cresça a árvore. Embora, no início, pareça uma solução horrível, sinto que você poderia abandonar a busca de folhas muito caras usando algumas heurísticas e podas ...