[問題] 有關一組數字組合相加的問題

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