贪婪算法：成本最小化

我正在用我写的贪婪算法挣扎;我知道我的算法是不完整的，但我真的不知道改进它：贪婪算法：成本最小化

Algorithme minCost() 

while j<n (while all the licences have not been yet bought) 
j=next licence bought 
If the licence of the current month is available then 
buy 
EndIf 
EndWhile

这个问题的提法：向市场推出各种产品，公司需要“N”许可证。由于某些法律规定，每个月不能获得一个以上的许可证。另外，许可费用每个月增加。事实上，虽然目前每种许可证的成本为100.00美元，但许可证j的成本（1≤j≤n）每月增加rj> 1（rj是参数）。换句话说，购买前四个月的许可费用为100r4，而在第五个月的收购费用则为100美元（r3）^ 5。最后，我们假设ri对于不同的j是不同的。接下来的问题是，对于一组给定的rj（1≤j≤n），以什么顺序购买“n”个许可证来最小化总体拥有成本。 1.使用贪婪方法开发多项式算法来解决这个问题。在最坏的情况下分析你的算法。 2.证明你的算法很好地返回最优解。 3.说明你在下列情况下的算法：N = 3，R1 = 3，R 2 = 4，R3 = 2

感谢

来源

2011-04-12 cProg

这显然是一个家庭作业问题。请分享您尝试过的内容，以及您正在努力解决的问题。您的算法在当前形式中没有太大意义，因为'j'是一个数字（在比较行上），但是它会变成下一行的许可证。 – 2011-04-12 23:45:18

大家好，直觉上，我可以说解决方案是首先选择成本最高的rj。这是我的算法： 'code' 算法minCost（A [1 ... n]空表来存储所选的许可证） while j cProg 2011-04-13 00:27:50

Algorithme minCout(A[1, ..., n], B[]) 
//A[1, ..., n]: table storing the rj values of the licenses cost 
//B[]: empty table to store selected licences cost for buy 
QuickSort(A[1, ..., n]) 
//A[1, ..., n] is now sorted in decreasing order 

while j < n (while all the licences have not been yet bought) do 
    for i ← 1 to n (Check all the available licences cost) do 
    if ri < ri+1 (choose the highest license cost) then 
    A[i ] = i + 1 (buy now the highest cost licence) 
    end 
    j = j + 1 (check the next licence to buy) 
    end 
    end 
Return A[i]

通常的许可证的数量必须以较长的下降，因为我选择成本最高的许可证并将它们存储在表B中。另外，当我检查许可证的成本时，我不得再次检查表A的全部部分。然后，我该如何编写一个这个算法的递归版本可以让我考虑我刚刚提到的内容？谢谢。

来源

2011-04-14 02:38:40 cProg

对不起？你能解释更多吗？我不明白什么是“反例”。 – cProg 2011-04-14 02:58:58

nvm，正在考虑问题的一般化版本 – 2011-04-14 03:06:54

贪婪算法：成本最小化

回答

相关问题