请稍等 ...
×

采纳答案成功!

向帮助你的同学说点啥吧!感谢那些助人为乐的人

关于非int类型求解

就以本章内容为例, 如果我们给的数组是带小数的,也就是nums里是带小数的 , 那么当我们定义状态的时候, 假如s表示数组和的一半,那么我们就不能用memo[n][s]来表示 选n个数使得n个数之和等于s,因为s是带小数的 数组表示的话 行列应该都不带小数。那么在这种情况下,我们该怎么定义状态和用数组来表示memo或dp呢?
就比如零钱换整这个问题, 如果给的零钱coins里面不是整数,而是带小数的,比如一分 一毛 一块这种,那这个时候还能用dp吗,用的话那个数组该怎么定义呢?谢谢老师!

正在回答 回答被采纳积分+3

1回答

liuyubobobo 2020-10-12 06:02:28

对于你举的换零钱的例子,我们应该将 coins 里的小数转换成整数。因为零钱的精度最多到达“分”的水平,所以所有的数据乘以 10,也就是用分来表示钱,就 ok 了。


更一般的,如果数据是任意小数的话,不能使用这种 dp 方法解决。此时,背包问题是一个 np 难的问题。


继续加油!:)

0 回复 有任何疑惑可以回复我~
问题已解决,确定采纳
还有疑问,暂不采纳
意见反馈 帮助中心 APP下载
官方微信