注意:这是对现实生活中有关对SWF文件中的记录进行排序的问题的抽象措词。一个解决方案将帮助我改善开源应用程序。
鲍勃(Bob)有一间商店，并想进行销售。他的商店有许多产品，并且每种库存产品都有一定数量的单位数量。他还具有许多在架子上安装的价格标签(与产品数量一样多)，并且已经在价格标签上打印了价格。他可以在任何产品上贴上任何价格标签(该产品的全部库存中某一产品的统一价格)，但是某些产品还有其他限制-任何此类产品可能都不比某些其他产品便宜。
您必须找到如何安排价格标签的方法，以使鲍勃所有商品的总成本尽可能低。总成本是每个产品分配的价格标签的总和乘以该产品的库存数量。
鉴于:
该程序必须找到:
满足条件:
请注意，如果不是针对第一个条件，则解决方案将是简单地按价格对标签进行分类，并按数量对产品进行分类，然后直接将二者匹配。
输入的典型值为N，K
这是为什么大多数简单的解决方案(包括拓 flutter 排序)不起作用的一个示例:
您有10个项目，数量从1到10，有10个价格标签，价格从$ 1到$ 10。有一个条件:数量为10的商品一定不能比数量为1的商品便宜。
最佳解决方案是:
Price, $ 1 2 3 4 5 6 7 8 9 10
Qty 9 8 7 6 1 10 5 4 3 2
总费用为249美元。如果将1,10对放置在任一极端附近，则总成本会更高。
最佳答案
对于一般情况，问题是NP完全的。这可以通过减少3分区来显示(这是仍然很强的NP完整版装箱)。
令w1，...，wn为3分区实例的对象的权重，令b为容器的大小，k = n / 3允许填充的容器的数量。因此，如果可以对对象进行分区，则每个分区有3个对象，则存在3个分区。
对于减少量，我们设置N = kb，每个bin由相同价格的b个价格标签表示(想想Pi每增加第b个标签就会增加)。令ti1≤i≤k为与第i个箱相对应的标签的价格。
对于每个wi，我们有一个数量为wi + 1的产品Sj(以下称其为wi的根产品)，而另一个wi-数量为1的产品Sj需要比Sj便宜(称为休假产品)。
对于ti =(2b +1)i，1≤i≤k，当且仅当Bob可以以2bΣ1≤i≤kti的价格出售时，才有3个分区:
因此，该解决方案的成本为2bΣ1≤i≤kti(因为价格为ti的产品总数为2b)。
首先要观察的是，在任何解决方案中，有3个以上的根产品具有相同的价格标签，对于每个“太多”的根产品，都有一个便宜的价格标签，其粘贴在少于3个根产品上。这比任何解决方案都更糟糕，因为每个价格标签仅存在3个根产品(如果存在)。
现在，仍然存在一个Bob's Sale的解决方案，其中每个价格带有3个根标签，但其休假产品不会带有相同的价格标签(垃圾箱有点流了)。
假设最昂贵的价格标签为wi的根产品加标签，而后者的标签产品更便宜。这意味着用最昂贵的价格标记的3个根标签wi，wj，wl的总和不等于b。因此，标有该价格的产品的总成本至少为2b + 1。
因此，这种解决方案的成本为tk(2b + 1)+一些其他分配成本。由于现有3分区的最佳成本为2bΣ1≤i≤kti，因此我们必须证明，刚刚考虑的情况更糟。如果tk> 2bΣ1≤i≤k-1ti就是这种情况(请注意，现在总和为k-1)。设置ti =(2b +1)i，1≤i≤k，就是这种情况。即使不是最昂贵的价格标签也是“坏”标签，但也包含其他标签，这同样适用。
因此，这是破坏性的部分；-)但是，如果不同价格标签的数量是一个常数，则可以使用动态编程在多项式时间内求解它。
关于algorithm - 问题:鲍勃的销售，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4898511/