Ottimizzazione combinatoria: riempire una borsa con sabbia

Question

Ottimizzazione combinatoria: riempire una borsa con sabbia

#1 da (1 voti)

5

Ho un interessante problema di ottimizzazione combinatoria del "mondo reale" che ho bisogno di risolvere a livello programmatico, tuttavia sono stato in grado di realizzare una buona strategia.

L'attività è simile al Problema di Knapsack tranne che ci sono ulteriori vincoli.

Le regole sono come segue:

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.

Considera questo esempio:

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

La soluzione solo è {0.5,1,1000,1000} che lascia N = {250,250,1,1.5} . I commentatori hanno affermato che l'ordinamento dell'elenco rende banale il problema, ma non è così.

... considera questo:

N = {1000,1000,250,250,1.5,1,1,0.5}
L = 4
X = 2002
Risposta : {0.5,1.5,1000,1000}, N → {250, 250, 1, 1}
Tieni presente che la scelta del set contiguo più piccolo nell'elenco ordinato che soddisfi il peso ( {250,1000,1000} ) viola la regola 4 poiché N → {250,248,1.5,1,1,0.5} ha un disallineamento più positivo.

Questo problema si presenta nell'e-commerce, specialmente quando si deve effettuare un pagamento con più forme di accesso prepagato ...

Qualcuno ha un buon approccio matematico o programmatico a questo problema?

algorithms optimization

posta Don Scott 06.12.2015 - 01:34

fonte

1 risposta

Leggi altre domande sui tag algorithms optimization

Alternative a Singletons per la cache di liste di dati? In Perlin noise, perché hanno bisogno di vettori e come usarli esattamente?

score 1 · Answer 1

Va bene ... sembra divertente quindi ci proverò. In codice pseudo c orribilmente sciatto:

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!
        }
    }

Ora ... Probabilmente ho avuto parecchi errori di battitura, non ho creato la funzione ricorsiva per scavalcare l'albero delle possibili combinazioni e aggiungerli all'array, correre attraverso ogni combinazione possibile è orribilmente inefficiente, e ovviamente "DING DING DING!" non è corretto C. Ma ... penso che tu abbia l'idea di base.