确定分发这些优惠券的最佳方式的算法是什么？

Here is my problem. Imagine I am buying 3 different items, and I have up to 5 coupons. The coupons are interchangeable, but worth different amounts when used on different items.

这是我的问题。想象一下,我正在购买3种不同的商品,而且我最多可以购买5张优惠券。优惠券可以互换,但在不同的物品上使用时价值不同。

Here is the matrix which gives the result of spending different numbers of coupons on different items:

这是矩阵,它给出了在不同项目上花费不同数量的优惠券的结果:

coupons:    1         2         3         4         5
item 1      $10 off   $15 off
item 2                $5 off    $15 off   $25 off   $35 off
item 3      $2 off

I have manually worked out the best actions for this example:

我已手动制定了此示例的最佳操作:

If I have 1 coupon, item 1 gets it for $10 off

如果我有1张优惠券,则第1件可获得10美元优惠券

If I have 2 coupons, item 1 gets them for $15 off

如果我有2张优惠券,则第1项可获得15美元优惠券

If I have 3 coupons, item 1 gets 2, and item 3 gets 1, for $17 off

如果我有3张优惠券,则第1项获得2,第3项获得1,只需17美元

If I have 4 coupons, then either:
- Item 1 gets 1 and item 2 gets 3 for a total of $25 off, or
- Item 2 gets all 4 for $25 off.

如果我有4张优惠券,那么:项目1获得1,第2项获得3,总共25美元,或者第2项获得全部4优惠25美元。

If I have 5 coupons, then item 2 gets all 5 for $35 off.

如果我有5张优惠券,则第2项将获得全部5张优惠券,价格为35美元。

However, I need to develop a general algorithm which will handle different matrices and any number of items and coupons.

但是,我需要开发一种通用算法来处理不同的矩阵和任意数量的项目和优惠券。

I suspect I will need to iterate through every possible combination to find the best price for n coupons. Does anyone here have any ideas?

我怀疑我需要遍历每个可能的组合,以找到n个优惠券的最佳价格。这里有没有人有任何想法?

6 个解决方案

#1

This seems like a good candidate for dynamic programming:

这似乎是动态编程的一个很好的候选者:

//int[,] discountTable = new int[NumItems][NumCoupons+1]

// bestDiscount[i][c] means the best discount if you can spend c coupons on items 0..i
int[,] bestDiscount = new int[NumItems][NumCoupons+1];

// the best discount for a set of one item is just use the all of the coupons on it
for (int c=1; c<=MaxNumCoupons; c++)
    bestDiscount[0, c] = discountTable[0, c];

// the best discount for [i, c] is spending x coupons on items 0..i-1, and c-x coupons on item i
for (int i=1; i<NumItems; i++)
    for (int c=1; c<=NumCoupons; c++)
        for (int x=0; x<c; x++)
            bestDiscount[i, c] = Math.Max(bestDiscount[i, c], bestDiscount[i-1, x] + discountTable[i, c-x]);

At the end of this, the best discount will be the highest value of bestDiscount[NumItems][x]. To rebuild the tree, follow the graph backwards:

在此结束时,最佳折扣将是bestDiscount [NumItems] [x]的最高值。要重建树,请向后按图:

edit to add algorithm:

编辑添加算法:

//int couponsLeft;

for (int i=NumItems-1; i>=0; i++)
{
    int bestSpend = 0;
    for (int c=1; c<=couponsLeft; c++)
        if (bestDiscount[i, couponsLeft - c] > bestDiscount[i, couponsLeft - bestSpend])
            bestSpend = c;

    if (i == NumItems - 1)
        Console.WriteLine("Had {0} coupons left over", bestSpend);
    else
        Console.WriteLine("Spent {0} coupons on item {1}", bestSpend, i+1);

    couponsLeft -= bestSpend;
}
Console.WriteLine("Spent {0} coupons on item 0", couponsLeft);

Storing the graph in your data structure is also a good way, but that was the way I had thought of.

在您的数据结构中存储图形也是一种好方法,但这是我想到的方式。

#2

It's the Knapsack problem, or rather a variation of it. Doing some research on algorithms related to this problem will point you in the best direction.

这是背包问题,或者更确切地说是它的变体。对与此问题相关的算法进行一些研究将指出您的最佳方向。

#3

I think dynamic programming should do this. Basically, you keep track of an array A[n, c] whose values mean the optimal discount while buying the n first items having spent c coupons. The values for a[n, 0] should be 0 for all values of n, so that is a good start. Also, A[0, c] is 0 for all c.

我认为动态编程应该这样做。基本上,你跟踪一个数组A [n,c],其数值意味着最优惠的折扣,而购买n个第一项消费c优惠券。对于n的所有值,[n,0]的值应为0,因此这是一个好的开始。此外,对于所有c,A [0,c]为0。

When you evaluate A[n,c], you loop over all discount offers for item n, and add the discount for that particular offer to A[n-1,c-p] where p is the price in coupons for this particular discount. A[n-1, c-p] must of course be calculated (in the same way) prior to this. Keep the best combination and store in the array.

当您评估A [n,c]时,您循环覆盖项目n的所有折扣优惠,并将该特定优惠的折扣添加到A [n-1,c-p],其中p是此特定折扣的优惠券价格。当然必须在此之前计算[n-1,c-p](以相同的方式)。保持最佳组合并存储在阵列中。

A recursive implementation would probably give the cleanest implementation. In that case, you should find the answer in A[N,C] where N is the total number of items and C is the total number of available coupons.

递归实现可能会提供最干净的实现。在这种情况下,您应该在A [N,C]中找到答案,其中N是项目总数,C是可用优惠券的总数。

#4

This can be written as a linear programming problem. For most 'typical' problems, the simplex method is a fast, relatively simple way to solve such problems, or there are open source LP solvers available.

这可以写成线性编程问题。对于大多数“典型”问题,单纯形法是解决此类问题的快速,相对简单的方法,或者有可用的开源LP求解器。

For your example:

对于你的例子:

Let 0 <= xi <= 1

设0 <= xi <= 1

x1 = One if one coupon is spent on item 1, zero otherwise

x1 =如果在项目1上花费一个优惠券,则为零,否则为零

x2 = One if two coupons are spent on item 1, zero otherwise

x2 =如果在项目1上花费两张优惠券,则为一,否则为零

x3 = One if one coupon is spent on item 2, zero otherwise

x3 =如果在第2项上花费一张优惠券,则为零,否则为零

x4 = One if two coupons are spent on item 2, zero otherwise

x4 =如果在第2项上花费两张优惠券,则为一,否则为零

x5 = One if three coupons are spent on item 3, zero otherwise

x5 =如果在项目3上花费三张优惠券,则为一,否则为零

Assume that if I spend two coupons on item 1, then both x1 and x2 are one. This implies the constraint

假设我在第1项上花了两张优惠券,那么x1和x2都是一张。这意味着约束

x1 >= x2

x1> = x2

With similar constraints for the other items, e.g.,

对于其他项目具有类似的约束,例如,

x3 >= x4

x3> = x4

x4 >= x5

x4> = x5

The amount saved is

节省的金额是

Saved = 10 x1 + 5 x2 + 0 x3 + 5 x4 + 10 x5 + ...

已保存= 10 x1 + 5 x2 + 0 x3 + 5 x4 + 10 x5 + ...

If you want to find the most money saved with a fixed number of coupons, then you want to minimize Saved subject to the constraints above and the additional constraint:

如果您想找到使用固定数量的优惠券保存的最多钱,那么您希望最小化保存受上述约束和附加约束:

coupon count = x1 + x2 + x3 + ...

优惠券数= x1 + x2 + x3 + ......

This works for any matrix and number of items. Changing notation (and feeling sad that I can't do subscripts), let 0 <= y_ij <= 1 be one if j coupons are spent on item number i. The we have the constraints

这适用于任何矩阵和项目数。改变符号(并且感到难过,我不能做下标),如果j项优惠券花在项目编号i上,则让0 <= y_ij <= 1。我们有约束

y_i(j-1) >= y_ij

y_i(j-1)> = y_ij

If the amount saved from spending j coupons on item i is M_ij, where we define M_i0 = 0, then maximize

如果在项目i上花费j优惠券节省的金额是M_ij,我们在其中定义M_i0 = 0,则最大化

Saved = Sum_ij (M_ij - M_i(j-1)) y_ij

保存= Sum_ij(M_ij - M_i(j-1))y_ij

subject to the above constraints and

受上述限制和约束

coupon count = Sum_ij y_ij

优惠券数量= Sum_ij y_ij

(The italics formatting doesn't seem to be working here)

(斜体格式似乎不起作用)

#5

I suspect some kind of sorted list for memoizing each coupon-count can help here.

我怀疑用于记忆每个优惠券计数的某种排序列表可以在这里提供帮助。

for example, if you have 4 coupons, the optimum is possibly:

例如,如果您有4张优惠券,最佳可能是:

using all 4 on something. You have to check all these new prices.

在所有东西上使用全部4。你必须检查所有这些新价格。

using 3 and 1. either the 3-item is the optimal solution for 3 coupons, or that item overlaps with the three top choices for 1-coupon items, in which case you need to find the best combination of one of the three best 1-coupon and 3-coupon items.

使用3和1. 3项是3个优惠券的最佳解决方案,或者该项目与1个优惠券项目的三个最佳选择重叠,在这种情况下,您需要找到三个最佳选项之一的最佳组合 - 优惠券和3优惠券。

using 2 and 2. find top 3 2-items. if #1 and #2 overlap, #1 and #3 , unless they also overlap, in which case #2 and #3 don't.

使用2和2.找到前3个2项。如果#1和#2重叠,#1和#3,除非它们也重叠,在这种情况下#2和#3不重叠。

this answer is pretty vague.. I need to put more thought into it.

这个答案很模糊。我需要多考虑一下。

#6

This problem is similar in concept to the Traveling Salesman problem where O(n!) is the best for finding the optimal solution. There are several shortcuts that can be taken but they required lots and lots of time to discover, which I doubt you have.

这个问题在概念上类似于旅行商问题,其中O(n!)是找到最优解的最佳选择。有几个快捷方式可以采取,但他们需要很多很多时间来发现,我怀疑你有。

Checking each possible combination is going to be the best use of your time, assuming we are dealing with small numbers of coupons. Make the client wait a bit instead of you spending years on it.

假设我们处理的是少量优惠券,那么检查每种可能的组合将最有效地利用您的时间。让客户稍等一下,而不是花费数年时间。

#1