5

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?

  • Constraint 4 seems to mean that you want to pour the buckets in size order from smallest to largest. Constraint 5 seems to make no sense at all, since all buckets are equally fungible. – A. I. Breveleri Dec 6 '15 at 2:12
  • 2
    As you are allowed to pour a partial bucket, the problem isn't all that interesting. You can just always pour from smallest/lightest to biggest. The constraint that the partial bucket must be the last one isn't a serious constraint. The only reason to pour a partial bucket is because the full bucket would over-fill the sack, but that also means that after the partial bucket, the sack is full. – Bart van Ingen Schenau Dec 6 '15 at 8:00
  • I have clarified the problem, which I think should clear up your comments. – Don Scott Dec 6 '15 at 17:14
  • 2
    I don't think you've clarified it so much as added a new and very important constraint "while maximizing negative skew of the remainder set". Makes me wonder what else you've left out. – A. I. Breveleri Dec 6 '15 at 23:10
  • 1
    @A.I.Breveleri The problem as currently written represents the real world case as best as I can qualify. The negative skew could have been inferred by my earlier description, however this is obviously more clear. – Don Scott Dec 6 '15 at 23:14
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.