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

Question

这是我的问题。假设我要购买 3 种不同的商品，并且我有多达 5 张优惠券。优惠券可以互换，但用于不同元素时值(value)不同。

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

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

我已手动计算出此示例的最佳操作:

• 如果我有 1 张优惠券，商品 1 可享受 10 美元的折扣
• 如果我有 2 张优惠券，第 1 项可享受 15 美元的折扣
• 如果我有 3 张优惠券，第 1 件得到 2 张，第 3 件得到 1 张，减 17 美元
• 如果我有 4 张优惠券，则其中之一:
  • 商品 1 减 1 件，商品 2 减 3 件，总共减价 25 美元，或者
  • 第 2 件商品全部 4 件减 25 美元。
• 如果我有 5 张优惠券，那么商品 2 可以全减 35 美元。

但是，我需要开发一种通用算法来处理不同的矩阵以及任意数量的商品和优惠券。

我怀疑我需要遍历所有可能的组合来找到 n 优惠券的最佳价格。这里有人有什么想法吗？

Answer 1

这似乎是动态规划的一个很好的候选者:

//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]);

最后，最佳折扣将是 bestDiscount[NumItems][x] 的最高值。要重建树，请向后看图:

编辑添加算法:

//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);

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