Otimização Combinatória: Preenchendo um Saco com Areia

Question

Otimização Combinatória: Preenchendo um Saco com Areia

#1 resposta do (1 votos)

5

Eu tenho um interessante problema de otimização combinatória "real-world" que eu preciso resolver programaticamente, no entanto, eu ainda fui capaz de esboçar uma boa estratégia.

A tarefa é semelhante ao Problema do Alforje , exceto que existem restrições adicionais.

As regras são as seguintes:

You must must fill a bag with weight X of sand.

You have N buckets of sand each with a random positive weight.

You may pour up to L buckets into the bag, where L is greater than one. All buckets poured must be poured in their entirety, except for the final one, in which the remainder will be left for future iterations of the problem.

You wish to empty completely as many buckets as possible, while maximizing negative skew of the remainder set.

You may not over or under-fill the bag, but you may assume that there is sufficient sand in the heaviest L buckets to satisfy the request.

Considere este exemplo:

N = {1000,1000,250,250,1,1,1,0.5}
L = 4
X = 2000

A solução somente é {0.5,1,1000,1000} deixando N = {250,250,1,1.5} . Os comentadores afirmaram que classificar a lista torna o problema trivial, mas isso não é verdade.

... considere isto:

N = {1000,1000,250,250,1.5,1,1,0.5}
L = 4
X = 2002
Responder : {0.5,1.5,1000,1000}, N → {250, 250, 1, 1}
Observe que escolher o menor conjunto contíguo na lista ordenada que satisfaz o peso ( {250,1000,1000} ) viola a regra 4, pois N → {250,248,1.5,1,1,0.5} tem uma inclinação mais positiva.

Este problema se apresenta no e-commerce, especialmente quando um pagamento é feito com várias formas de acesso pré-pago ...

Alguém tem uma boa abordagem matemática ou programática para esse problema?

algorithms optimization

por Don Scott 06.12.2015 / 01:34

fonte

1 resposta

Tags algorithms optimization

Elasticsearch e combinação de banco de dados relacional No ruído Perlin, por que precisamos de vetores e como usá-los exatamente?

score 1 · Answer 1

Ok ... Isso parece divertido, então vou tentar. No código pseudo c horrivelmente desleixado:

int bagGoal = X;
int numBuckets = N;
int bucket[numBuckets] = {N1,...};
int maxPours = L;
int maxCombinations = pow(2,numBuckets);

/* Create a 2 dimensional array of combinations of bucket pour quantities
   and zero it all */
int pourList[maxPours][maxCombinations] = {0};

/* Fill the above array with all possible combinations of buckets in
   which the maximum number of pours (maxPours) or less is greater than
   the amount you want in the bag (bagGoal) */
int currentPour = 0;
int temporaryBagQuantity = 0;
recursivelyAddBucketsToArray();

/* Sort pourList descending by number of buckets per combination */
qsort(&pourList, maxCombinations, size_of pourList[maxPours], compare);

/* Step through pourList looking for the first combination with a negative
   skew */
for(int counter = 0; counter < maxCombinations; counter++)
    {
    /* create an array of the buckets remaining after this combination
       is removed */
    int remainingBuckets[numBuckets] = {0};
    int currentBucket = 0;
    for(int counter2 = 0; counter2 < maxPours; counter2++)
        {
            for(int counter3 = 0; counter3 < numBuckets; counter3++)
            {
            if(bucket[counter3] == pourList[counter2][counter])
                break;
            remainingBuckets[currentBucket] = bucket[counter3];
            currentBucket++;
            }
        }
    if(remainingBuckets are negatively skewed)
        {
        DING DING DING! We have the winner!
        }
    }

Agora ... Eu provavelmente tenho vários erros lá, eu não criei a função recursiva para percorrer a árvore de combinações possíveis e adicioná-los à matriz, percorrer todas as combinações possíveis é terrivelmente ineficiente e obviamente "DING DING DING!" não é apropriado C. Mas ... eu acho que você tem a idéia básica.