关于非int类型求解
来源：9-7 面试中的0-1背包问题 Partition Equal Subset Sum
慕粉4405724
2020-10-12
就以本章内容为例， 如果我们给的数组是带小数的，也就是nums里是带小数的 ， 那么当我们定义状态的时候, 假如s表示数组和的一半，那么我们就不能用memo[n][s]来表示 选n个数使得n个数之和等于s，因为s是带小数的 数组表示的话 行列应该都不带小数。那么在这种情况下，我们该怎么定义状态和用数组来表示memo或dp呢？
就比如零钱换整这个问题， 如果给的零钱coins里面不是整数，而是带小数的，比如一分 一毛 一块这种，那这个时候还能用dp吗，用的话那个数组该怎么定义呢？谢谢老师！
写回答
1回答
-
liuyubobobo
2020-10-12
对于你举的换零钱的例子，我们应该将 coins 里的小数转换成整数。因为零钱的精度最多到达“分”的水平，所以所有的数据乘以 10，也就是用分来表示钱，就 ok 了。
更一般的，如果数据是任意小数的话，不能使用这种 dp 方法解决。此时，背包问题是一个 np 难的问题。
继续加油！：）
00
相似问题