[問題] 非負整數解集合問題

作者: hexjacal (黑麻糬)   2014-09-16 23:25:42
開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
Dev C++
問題(Question):
解出 X_1 + X_2 + ... + X_n = 5 的非負整數解 (n>=5)
存成 (n+4)/(n!*4!) * n 的矩陣
預期的正確結果(Expected Output):
Ex. n=7
那解集合有
5 0 0 0 0 0 0
4 1 0 0 0 0 0
4 0 1 0 0 0 0
...
0 0 0 0 0 1 4
0 0 0 0 0 0 5
補充說明(Supplement):
爬文找到版友滴文章,似乎都是以背包問題印出結果
且不考慮同一解的排列,但在我的問題中變數是不同的
i.e. X_1=5, X_2~X_7=0; ... ;X_1~X_6=0,X_7=5 是視為不同解
目前想用遞迴背包問題的程式
在原解尾端補零後,用 Algorithm 裡頭的 Permutation 嘗試解決
但總覺得一定有更快的方法,不曉得版大們能不能給一些建議呢?
作者: Feis (永遠睡不著 @@)   2014-09-16 23:30:00
直接遞迴解. 看不出有甚麼藥特殊處理的
作者: fenzhang (分帳)   2014-09-17 11:00:00
你的快的定義是時間複雜度還是寫code的速度?

Links booklink

Contact Us: admin [ a t ] ucptt.com