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

[linkone (小豆豆)]

例如 容量是259 給定 81 58 42 33 61

如何求出最告進容量而且是由給定的數字組合出來的的值

... 一開始以為先排序然後由大加到小就可以了...真天真= =

不曉得要用到啥技巧? 麻煩各位嚕

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.116.216.83
推 suhorng:看起來像dynamic programming, 應該可以算零錢問題的一種?
→ suhorng:"組合"只能是加的嗎 ? 可以是減的嗎 ?
→ linkone:只能是加的 應該是DP沒錯 但是不太清楚如何去實現
→ suhorng:有數字範圍嗎~  如果直接用零錢問題DP, 最後搜答案呢 ?
→ linkone:數字是100到5000 沒做過零錢問題所以不太懂~.~
→ linkone:目前有想說要用拿掉的方式做做看~
推 suhorng:假設 b[i][j] 代表能不能用前 i 個數字組合出數值 j
→ suhorng:那可以得到遞迴式 c[i][j] = c[i-1][j] | c[i][j-v[i]];
→ linkone:感謝你 測試中~