作者linkone (小豆豆)
看板Prob_Solve
標題[問題] 有關一組數字組合相加的問題
時間Sun Aug 22 19:31:47 2010
例如 容量是259 給定 81 58 42 33 61
如何求出最告進容量而且是由給定的數字組合出來的的值
... 一開始以為先排序然後由大加到小就可以了...真天真= =
不曉得要用到啥技巧? 麻煩各位嚕
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.116.216.83
1F：推 suhorng:看起來像dynamic programming, 應該可以算零錢問題的一種? 08/22 19:45
2F：→ suhorng:"組合"只能是加的嗎 ? 可以是減的嗎 ? 08/22 19:45
3F：→ linkone:只能是加的 應該是DP沒錯 但是不太清楚如何去實現 08/22 20:11
4F：→ suhorng:有數字範圍嗎~ 如果直接用零錢問題DP, 最後搜答案呢 ? 08/22 20:20
5F：→ linkone:數字是100到5000 沒做過零錢問題所以不太懂~.~ 08/22 20:30
6F：→ linkone:目前有想說要用拿掉的方式做做看~ 08/22 20:32
7F：推 suhorng:假設 b[i][j] 代表能不能用前 i 個數字組合出數值 j 08/22 20:34
8F：→ suhorng:那可以得到遞迴式 c[i][j] = c[i-1][j] | c[i][j-v[i]]; 08/22 20:36
9F：→ linkone:感謝你 測試中~ 08/23 16:16