Combinatorial Optimization: Filling a Bag with Sand

  softwareengineering

I have an interesting “real-world” combinatorial optimization problem that I need to solve programmatically, however I have yet been able to whiteboard a good strategy.

The task is similar to the Knapsack Problem except there are additional constraints.

The Rules are as Follows:

  1. You must must fill a bag with weight X of sand.
  2. You have N buckets of sand each with a random positive weight.
  3. 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.
  4. You wish to empty completely as many buckets as possible, while maximizing negative skew of the remainder set.
  5. 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.

Consider this Example:

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

The only solution is {0.5,1,1000,1000} leaving N = {250,250,1,1.5}. Commenters have asserted that sorting the list make the problem trivial, but this is not so.

… consider this:

  • N = {1000,1000,250,250,1.5,1,1,0.5}
  • L = 4
  • X = 2002
  • Answer: {0.5,1.5,1000,1000}, N → {250, 250, 1, 1}
  • Note that choosing the smallest contiguous set in the ordered list which satisfies the weight ({250,1000,1000}) violates rule 4 as N → {250,248,1.5,1,1,0.5}has a more positive skew.

This problem presents itself in e-commerce, especially when a payment is to be made with multiple forms of prepaid access…

Does anyone have a good mathematical or programmatic approach to this problem?

  • algorithms
  • optimization

5

Okay… This looks fun so I’ll try. In horribly sloppy pseudo c code:

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

Now… I’ve probably got several typos in there, I didn’t create the recursive function to step through the tree of possible combinations and add them to the array, running through every possible combination is horribly inefficient, and obviously “DING DING DING!” isn’t proper C. But…I think you get the basic idea.

LEAVE A COMMENT