什么是算法来确定分发这些优惠券的最佳方法？ [英] What is the algorithm to determine the best way to distribute these coupons?

问题描述

下面是我的问题。想象一下，我买3个不同的项目，我有多达5优惠券。优惠券是可以互换的，但值得不同的数额在不同的项目使用的时候。

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.

下面是矩阵这给不同的项目花费不同数量的优惠券的结果：

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:

• 如果我有1优惠券，1项获得它关闭$ 10个
• 如果我有2个优惠券，1项获得他们为$ 15关
• 如果我有3优惠券，第1项获得2和第3项得到1，为$ 17日关闭
• 如果我有4个优惠券，然后点击或者：
  • 在第1项获得1和2项获得3共计$ 25关，或
  • 第2项得到所有4 $ 25个了。
  • If I have 1 coupon, item 1 gets it for $10 off
  • If I have 2 coupons, item 1 gets them for $15 off
  • If I have 3 coupons, item 1 gets 2, and item 3 gets 1, for $17 off
  • 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.

    不过，我需要制定一个总的算法，它将处理不同矩阵和任意数量的项目和优惠券。

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

    我怀疑我会需要通过各种可能的组合，重复，以找到最好的价格的 N 的优惠券。没有人在这里有什么想法？

    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?

    推荐答案

    这似乎是一个很好的候选人，动态规划：

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

    在本月底，最好的折扣会bestDiscount [numItems的] [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:

    编辑添加算法：

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

    这篇关于什么是算法来确定分发这些优惠券的最佳方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！