作者orangeforest ()
看板MATLAB
標題[討論] 有條件的排列組合
時間Wed Jul 29 15:03:11 2015
最近為了解決一個關於有條件限制的排列組合問題，所以用了簡單的暴力解決
但是後來遇到更龐大的問題就會超出記憶體了，
有試過用基因演算法也能得到解，但想用別的方式試試看
這邊敘述一下我想解決的問題
例如：有50個位於不同地點的工廠(有x,y座標)，
每個工廠各有不同的出貨量(50個廠總產量約4500)，
今天有兩台大卡車去載貨(每台可以載3000)
以下就是我的問題
1.將50廠分成2大群(給2台卡車)，每群總和最多3000
列出滿足條件的組合(數字不重複，組合也不重複)
例如: 1-2-3-4跟1-3-2-4是屬於同一種(組合重複)；也不可以1-2-2-3(數字重複)
2.依據座標計算組合裡的總距離 (也就是卡車載完群裡所有工廠的距離)
我目前的想法是將兩個問題分成2個小程式
第一題 讓一個小矩陣中存2個數值 共50個矩陣 [編號 出貨量]
之後用nchoosek和randperm來求全部組合並算總出貨量
但問題在於不知道該50取幾當一群來計算總數，也難以檢查是否有組合重複，就卡住了..
第二題算簡單，只要第一題有解，套入距離公式後就能很快得到
以上問題還麻煩本版的高手們指教幫助了
附上部分資料的圖片
http://imgur.com/XLLl1ik
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.46.3.46
※ 文章網址: https://webptt.com/m.aspx?n=bbs/MATLAB/M.1438153395.A.25E.html
1F：→ celestialgod: 一行行把組合寫入檔案，再一行行讀入計算？ 07/29 15:40
2F：→ celestialgod: 組合應該從50取2開始找，找到50取25，一步步篩選不 07/29 15:42
3F：→ celestialgod: 要的組合 07/29 15:42
4F：→ orangeforest: 晚點試看看，不知道還有沒有什麼函數可以比較快計算 07/29 18:38
5F：→ orangeforest: ？ 07/29 18:38
6F：推 JamesChen: 函數只是幫妳寫好一套 routine 07/30 23:35
7F：→ JamesChen: 你如果要快 可能是要找有什麼演算法 07/30 23:35
8F：→ orangeforest: 的確是…目前看來用一些生物演算法的結果都比較好 07/31 17:35
9F：推 s4300026: 建議去programming版問演算法問題 08/04 21:58