[問題] 38個數字選取其中6個使其湊到某個值怎麼寫？

看板C_and_CPP作者 (WZXM)時間15年前 (2010/10/02 22:14), 編輯推噓7(7推 0噓 55→)
留言62則, 11人參與, 最新討論串1/1
想請問一下 現在我有38個數字 要任意選取其中6個 使其湊到某個值 38 其實這就是組合C 6 的問題 我將這38個數存成陣列後 要用如何的演算法？ 才可以將所有的可能跑過一遍 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 125.232.43.132
推
10/02 22:20, , 1F
動態規劃問題 01背包
10/02 22:20, 1F
推
10/02 22:46, , 2F
用遞迴
10/02 22:46, 2F
→
10/02 22:48, , 3F
背包問題是說不要超過那個負重 可是我要選的值恰好為
10/02 22:48, 3F
→
10/02 22:48, , 4F
某特定值
10/02 22:48, 4F
→
10/02 22:49, , 5F
遞迴的話 不知道要怎樣寫才可以跑過所有可能
10/02 22:49, 5F
→
10/02 23:07, , 6F
如果背包你覺得不行的話...那改看硬幣問題？
10/02 23:07, 6F
→
10/02 23:20, , 7F
10/02 23:20, 7F
→
10/02 23:54, , 8F
應該是你程式跑的那樣
10/02 23:54, 8F
推
10/03 00:33, , 9F
把背包問題的小於等於限制式改成等於
10/03 00:33, 9F
→
10/03 00:34, , 10F
也就是說相對應的程式部份, 也只要改那個小於等於就好了
10/03 00:34, 10F
→
10/03 00:45, , 11F
原來如此...
10/03 00:45, 11F
→
10/03 13:06, , 12F
ㄜ.. 請問樓樓上程式要怎麼把對應的程式部份的小於等於
10/03 13:06, 12F
→
10/03 13:06, , 13F
限制式改成等於 真是這樣嗎
10/03 13:06, 13F
推
10/03 13:18, , 14F
跟某個數相減取絕對值小於等於某誤差 XDD
10/03 13:18, 14F
推
10/03 13:33, , 15F
原本背包是 [前i個物品][重量不超過j元] 能取最大值
10/03 13:33, 15F
→
10/03 13:33, , 16F
現在一樣啊 只是變成：
10/03 13:33, 16F
→
10/03 13:34, , 17F
[前i個物品][使用j個][恰好湊出k元] = 能/不能 這樣
10/03 13:34, 17F
→
10/03 13:37, , 18F
而且只有 6 個, 還可以位運算優化把 [使用j個] 去掉
10/03 13:37, 18F
→
10/03 14:09, , 19F
喔 用三維dp去做阿 我原本想是把每個數都當成物品
10/03 14:09, 19F
→
10/03 14:10, , 20F
每個物品重量都是1 價值就是自己的數
10/03 14:10, 20F
→
10/03 14:12, , 21F
要找幾個數就找對應的背包重量就好了 6個數就找重量六
10/03 14:12, 21F
→
10/03 14:13, , 22F
然後在該重量找有沒有目標數 把table在dfs回去就得到
10/03 14:13, 22F
→
10/03 14:14, , 23F
結果了
10/03 14:14, 23F
→
10/03 15:00, , 24F
沒人回好無聊 如果用三維dp做程式就要大改絕對不只改
10/03 15:00, 24F
→
10/03 15:02, , 25F
"那個小於等於就好了"而且速度也慢多了（戰
10/03 15:02, 25F
→
10/03 15:03, , 26F
不妨試試下篇文章的方法,基本上,不需要DP.
10/03 15:03, 26F
推
10/03 15:05, , 27F
才6個數字也可以變成二維DP ww
10/03 15:05, 27F
→
10/03 15:05, , 28F
雖然那樣做本質上仍然是三維XD
10/03 15:05, 28F
→
10/03 15:17, , 29F
to:Y大基本下面那篇作法概念上就是窮舉法數字一多會慢吧
10/03 15:17, 29F
→
10/03 15:19, , 30F
慢是慢到哪裡去呢? 這是很普通的求組合啊.
10/03 15:19, 30F
→
10/03 15:23, , 31F
要產生c38取6種囉 的確是不大拉 （不戰了 我要出門了
10/03 15:23, 31F
→
10/03 15:25, , 32F
你講三維DB,實作方法百百種,怎樣做得對,怎做是錯,還待商榷.
10/03 15:25, 32F
→
10/03 15:25, , 33F
但是我講的方法只有一種,寫出來的程式也一個樣子. 然後,
10/03 15:25, 33F
→
10/03 15:26, , 34F
38取6你說要怕多慢呢? 你為了求快,但是方法卻沒辦法講清楚.
10/03 15:26, 34F
→
10/03 15:27, , 35F
沒人在跟你戰,只不過是,對於你想了一半的方法,你卻信誓旦旦
10/03 15:27, 35F
→
10/03 15:27, , 36F
覺得一定是最好最快. 我不懂,你這種信心是哪裡來的?
10/03 15:27, 36F
→
10/03 15:38, , 37F
我回應你是因為看到你15:00推的那二句.好,來談,你卻要跑了?
10/03 15:38, 37F
→
10/03 15:42, , 38F
( ￣ c￣)y▂ξ 來聊語法好不好...
10/03 15:42, 38F
→
10/03 17:24, , 39F
我回了喔
10/03 17:24, 39F
→
10/03 17:25, , 40F
請問一下我的方法哪裡不明確勒？
10/03 17:25, 40F
→
10/03 17:25, , 41F
算了不想用分身
10/03 17:25, 41F
→
10/03 17:27, , 42F
你的方法本來就是窮舉法 慢是事實 再這麼辯都不會變快
10/03 17:27, 42F
→
10/03 17:28, , 43F
況且我有說我的方法最好最快嗎？
10/03 17:28, 43F
→
10/03 20:10, , 44F
不是,快慢的問題是DP要解決的.而對我的方法來說,慢明明就無
10/03 20:10, 44F
→
10/03 20:10, , 45F
所謂. 他會強調快,基本是因為他DP怕人講慢.
10/03 20:10, 45F
→
10/03 20:11, , 46F
另外,你們可以讀讀本篇和下一篇二個討論串,會看到人們面對問
10/03 20:11, 46F
→
10/03 20:12, , 47F
題的一些態度:一開始考慮太嚴,設限很高,但是後來掙扎到某一
10/03 20:12, 47F
→
10/03 20:13, , 48F
個極限狀態時,突然就可以接受一些較普通的方法了.
10/03 20:13, 48F
→
10/03 20:13, , 49F
那麼,為什麼不一開始就先求有,再求好,就好了呢?
10/03 20:13, 49F
→
10/03 20:16, , 50F
netsphere你是用DP嗎? ok,就推文所看:第一,你沒有講到很具體
10/03 20:16, 50F
→
10/03 20:17, , 51F
的演算法,至少也沒有講到最核心的幾步驟.再來是,你沒有講總
10/03 20:17, 51F
→
10/03 20:18, , 52F
共要準備哪些提供DP的資料空間,哪些陣列對應哪些資料項目.
10/03 20:18, 52F
→
10/03 20:18, , 53F
我蠻肯定的是,知道同樣DP心法,二個人寫出來的程式是二種樣子
10/03 20:18, 53F
→
10/03 20:19, , 54F
程式流程不一樣,陣列配置不一樣.
10/03 20:19, 54F
→
10/03 20:19, , 55F
另外,就是一個與DP本身的存在有關的最大的問題. DP是說,本來
10/03 20:19, 55F
→
10/03 20:20, , 56F
對一個問題先有個普通的解,但這個解有些沒效率,所以用DP改寫
10/03 20:20, 56F
→
10/03 20:20, , 57F
成另一個等價的程式,一樣解決問題,同時把效率加強.
10/03 20:20, 57F
→
10/03 20:21, , 58F
在這一篇,原po問的是"程式怎麼寫",他連一個普通解都不知道.
10/03 20:21, 58F
推
10/03 20:21, , 59F
N大辛苦了...
10/03 20:21, 59F
→
10/03 20:22, , 60F
你認為在他不知道普通解怎麼寫的時候,能容易學到DP解怎麼寫?
10/03 20:22, 60F
→
10/03 20:22, , 61F
啊不小心斷到了真是抱歉
10/03 20:22, 61F
→
10/03 20:22, , 62F
ok,我寫完了. 我想我們可以寫一點程式,再來說誰好誰壞.
10/03 20:22, 62F
‣ 更多 WWWZZZXXXMMM 的文章
文章代碼(AID): #1Cfpv4tH (C_and_CPP)