作者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