Re: [問題]新手請教更好寫法

看板Python作者ThxThx (洗洗睡)時間6年前 (2018/12/01 22:55)推噓1(1推 0噓 5→)

留言6則, 2人參與討論串1/1

※ 引述《zz860619 (Kukuboo)》之銘言： : 各位大大晚安最近小弟在寫一個小專題 : 題目簡單說就是分配航段內航班給各個航空公司 : 譬如我這個航段裡總共有10個航班要分配給2個航空公司 : 這樣就有可能是（0,10) (1,9)以此類推 : 航班數跟航空公司小還好說，分配的航空公司一多，想求出每種可能性就要跑半天，不知 : 道有沒有更快求出的寫法？ : 以下是目前寫的 a就是當下的可能性 : total =4 #總共要分配的航班數 : num = 3 #分給幾家航空公司 : a = [0 for x in range(num)] : def per (fas_total,air_number,num): : if air_number == 1: : a[num-air_number] = fas_total : print(a) : print("========================") : else: : for i in range(fas_total+1): : a[num-air_number] = i : per(fas_total-i,air_number-1,num) : per(total,num,num) : 希望有人可以幫忙我一下，謝謝~ 針對你真正的問題「求所有可能組合中的最佳解」這個問題是NP-complete的問題（我想應該可以轉換成某種weighted vertex cover，還煩請高手指正）所以如果沒有更多條件的話，用暴力解（就是你現在的作法）不要太期待會有很快得到解答的方法。你可以想想看，光「航空公司含有航班數量」的組合就有H^m_n種可能（例如，你的範例會有11種），還要考慮航班的排列情況。比較好的方法是利用已知條件減少搜尋的數量。看你的code，你可能真正的code是把print那行改成計算cost的function。如果是這樣，那就是DFS的搜尋，也許可以減枝吧？在下一層遞迴前把不可能的情況跳過，可以少算很多。我的意思是，感覺你還沒有深入想想這個問題適合的演算法，就想優化code。錯誤的演算法在數量級太大的時候是不實際的。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.44.244.126 ※ 文章網址: https://www.ptt.cc/bbs/Python/M.1543676101.A.986.html