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:
- You must must fill a bag with weight
Xof sand.- You have
Nbuckets of sand each with a random positive weight.- You may pour up to
Lbuckets into the bag, whereLis 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
Lbuckets to satisfy the
request.
Consider this Example:
N = {1000,1000,250,250,1,1,1,0.5}L = 4X = 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 = 4X = 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 asN → {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?
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.