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

[ThxThx (洗洗睡)]

※ 引述《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
→ zz860619: 好的謝謝 我會再想想這個問題的解法
推 qwaszx780917: 聽起來很像整數規劃裡的指派問題 概念蠻簡單的建議
→ qwaszx780917: 可以看看 或是一些作業研究裡面比較適合的方法 應
→ qwaszx780917: 該把model列好 都會有現成的套件可以解 不過問題如
→ qwaszx780917: 果太大的話 效能考量上應該就建議用一些優化演算法
→ qwaszx780917:   個人淺見