组合优化:充沙袋

Question

我有一个有趣的“现实世界”组合优化问题，我需要通过编程来解决，但是我还能用白板写一个很好的策略。

该任务与背包问题类似，只是有附加的约束。

规则如下：

1. 你必须把重量为X的沙子装满袋子。
2. 你有一桶N沙子，每一桶都有一个随机的正重量。
3. 你可以把L桶倒进袋子里，那里的L大于一个。所有倒入的桶必须全部倒出，但最后一个桶除外，在最后一个桶中，剩下的将留给问题的未来迭代处理。
4. 您希望尽可能多地清空桶，同时最大化剩余集的负偏斜。
5. 您可以不超过或不足的袋子，但你可以假设有足够的沙子在最沉重的L桶，以满足要求。

考虑这个例子：

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

唯一的解决方案是{0.5,1,1000,1000}离开N = {250,250,1,1.5}。评论者声称，对列表进行排序会使问题变得微不足道，但事实并非如此。

...考虑一下：

• N = {1000,1000,250,250,1.5,1,1,0.5}
• L = 4
• X = 2002
• 答：{0.5,1.5,1000,1000}, N → {250, 250, 1, 1}
• 注意，在满足权重的有序列表中选择最小的连续集({250,1000,1000})违反了规则4，因为N → {250,248,1.5,1,1,0.5}具有更多的正偏斜。

这个问题出现在电子商务中，特别是当一笔款项是以多种形式的预付费方式支付时.

有人有一个很好的数学或编程方法来解决这个问题吗？

Answer 1

好吧..。这看起来很有趣所以我会试试的。在极其草率的伪c代码中：

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

现在..。我可能有几个排版，我没有创建递归函数来遍历可能组合的树，并将它们添加到数组中，运行每一个可能的组合都是非常低效的，显然是“丁仃丁！”不是真的，但是.我觉得你有基本的想法。