确定分配这些优惠券的最佳方式的算法是什么？
确定分配这些优惠券的最佳方式的算法是什么？
提问于 2009-01-08 21:57:31
这是我的问题。想象一下，我正在购买3种不同的物品，我有多达5张优惠券。优惠券是可互换的，但在不同的物品上使用时价值不同。
这是一个矩阵，它给出了在不同项目上花费不同数量的优惠券的结果：
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我已经为这个例子手工计算出了最佳的操作：
- 如果我有一张优惠券，第一项以10美元的价格买到。
- 如果我有两张优惠券，第一项就能以15美元的价格买到
- 如果我有3张优惠券，项目1得到2，第3项得到1，减价17美元
- 如果我有4张优惠券，那么，：
- 项目1得到1，第2项得到3，总共25美元折扣，或
- 第2项以25美元的价格获得全部4。
- 如果我有5张优惠券，那么第2项就能以35美元的价格全部买到。
然而，我需要开发一个通用的算法，它将处理不同的矩阵和任意数量的项目和优惠券。
我怀疑我将需要迭代每一个可能的组合，以找到最佳的价格n优惠券。这里有人有什么想法吗？
回答 6
Stack Overflow用户
回答已采纳
发布于 2009-01-08 22:39:02
这似乎是动态规划的一个很好的选择：
//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]);在这之后，最好的折扣将是bestDiscountNumItems的最高价值。要重建树，请向后遵循图表：
编辑以添加算法：
//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);将图形存储在数据结构中也是一种很好的方式，但这正是我所想到的方式。
Stack Overflow用户
发布于 2009-01-08 22:06:56
这是背包问题，或者说是它的一个变体。做一些与这个问题相关的算法的研究会给你指明最好的方向。
Stack Overflow用户
发布于 2009-01-08 22:15:11
我认为动态规划应该这么做。基本上，您可以跟踪一个数组An，c，它的值表示购买消费c优惠券的第n个项目时的最佳折扣。对于n的所有值，an，0的值应该是0，所以这是一个很好的开始。另外，A0，c对所有c都是0。
当您评估An，c，您循环所有的折扣优惠项目n，并将该特定优惠的折扣加到a-1，c-p，其中p是这个特定折扣的优惠券的价格。在此之前，必须(以同样的方式)计算a-1，c。保持最佳组合并存储在数组中。
递归实现可能会提供最干净的实现。在这种情况下，您应该在AN，C中找到答案，其中N是项目总数，C是可用优惠券的总数。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/426173
复制相关文章
相似问题
腾讯云开发者
