algorithm - 具有连续(非不同)约束的背包

Question

我看了Dynamic Programming - Kapsack Problem (YouTube) .但是，我正在解决一个稍微不同的问题，其中约束是预算、价格， double ，而不是整数。所以我想知道如何修改它？ Double 是“连续的”，不像整数，我可以有 1,2,3 ....我不认为我做 0.0, 0.1, 0.2 ...？

更新 1

我想通过乘以 100 将 double 转换为 int。钱只有 2 位小数。但这是否意味着值的范围会非常大？

更新 2

我需要解决的问题是:

Items have a price (double) & satisfaction (integer) value. I have a budget as a constraint and I need to maximize satisfaction value.

In the youtube video, the author created two 2d array like int[numItems][possibleCapacity(weight)]. Here, I can't as budget is a double not integer

Answer 1

如果您想使用任意精度的 float (即没有固定的小数位数)，并且这些不是分数，动态规划将不起作用。

动态规划的基础是存储特定输入的先前计算结果。因此，如果您使用任意精度的 float ，则实际上每个可能的 float 都需要无限的内存，当然，还需要进行无限的计算，这是不可能的，也不是最优的。

但是，如果这些数字具有固定的精度(如货币，只有两位小数)，您可以通过将它们相乘(如您所提到的)将它们转换为整数，然后解决背包问题平时。