輸入: 參數1,正數數組costs 參數2,正數數組profits 參數3, 正數k 參數4,正數m
costs[i]? ?表示i號項目的花費

profits[i]? 表示i號項目在扣除花費之后還能掙到的錢(利潤) k表示你不能并行、只能串行的最多 做k個項目 m表示你初始的資金

說明:你每做完一個項目,馬上獲得的收益,可以支持你去做下 一個 項目。

輸出: 你最后獲得的最大錢數。

思路：

1、定義項目類如下：

class program:def __init__(self,cost,profit):self.cost = costself.profit = profit

2、生成小根堆costMinHeap， 可以把具體的program放進costMinHeap中，根據Program的花費來組織小根堆，花費最少的program放在costMinHeap的堆頂

3、生成大根堆profitMaxHeap, 可以把具體的program放進profitMaxHeap中，根據Program的利潤來組織小根堆，利潤最多的Program放在profitMaxHeap的堆頂

4、根據costs和profits數組，可以得到所有的program，把所有的program放進costMinHeap

5、根據當前的資金W，來解鎖costMinHeap中的項目，只要是花費小于或等于W的項目，就從costMinHeap中彈出，放入profitMaxHeap。因為costMinHeap是小根堆，所以依次彈出program，知道costMinHeap為空或者剩下項目的花費都大于W,彈出過程停止。每一個從costMinHeap彈出的program，都進入profitMaxHeap。進入步驟6

6、profitMaxHeap裝著所有可以被考慮和被解鎖的項目

1）如果經歷了步驟5之后，發現profitMaxHeap為空，首先說明當前資金W并沒有解鎖出任何項目，其次說明目前已經沒有任何項目可以挑選啦，直接返回W

2）如果經歷了步驟5解鎖之后，發現profitMaxHeap不為空。選擇位于profitMaxHeap堆頂的那個項目完成，標記為programBest，因為在所有可以被考慮的項目中，profitMaxHeap堆頂的項目一定是獲得利潤最多的項目。完成programBest之后，可以獲得programBest的利潤。所以W＋＝programBest.profit。然后重復步驟5，進行新一輪的解鎖。

7、如果步驟6進行的過程中沒有返回。那么做完K個項目后，返回W

"""偽代碼如下"""class Program:def __init__(self,cost,profit):self.cost = costself.profit = profitdef getMaxmoney(W,K,costs,profits):if W < 1 or K < 0 or costs == None or profits == None or len(costs) != len(profits):return W"""項目花費小根堆，花費最少的項目在頂部"""costMinHeap = CostMinHeap()"""項目利潤大根堆，利潤最大的項目在頂部"""profitMaxHeap = ProfitMaxHeap()"""所有項目都進花費小根堆"""for i in range(len(costs)):costMinHeap.add(costs[i],profits[i])"""依次做k個項目"""for i in range(K+1):"""當前資金為W,在項目花費小根堆里所有花費小于或等于W的項目，都可以考慮"""while (!costMinHeap.isEmpty() and costMinHeap.peek().cost <= W):"""把可以考慮的項目都放進項目利潤大根堆里"""profitMaxHeap.add(costMinHeap.poll())"""如果此時項目利潤大根堆為空，說明可以考慮的項目為空，說明當前資金W已經無法解鎖任何項目，直接返回W"""if (profitMaxHeap.isEmpty()):return WW += profitMaxHeap.poll().profitreturn W

?

總結

以上是生活随笔為你收集整理的做项目的最大收益的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。