Combinatorial Optimization: Filling a Bag with Sand

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. Commented Dec 6, 2015 at 2:12
• 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. Commented Dec 6, 2015 at 8:00
• I have clarified the problem, which I think should clear up your comments. Commented Dec 6, 2015 at 17:14
• 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. Commented Dec 6, 2015 at 23:10
• @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. Commented Dec 6, 2015 at 23:14

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;

/* 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.