algorithm - 非整数界情况下的动态规划

Question

你有 n 个项目作为输入，其中项目 i 具有正实值权重 wi 和 a正整数值 vi。您还获得了正实值容量 W。请注意，权重不必是完整的。给出一个返回子集值的动态规划算法总值(value)最大的项目受制于子集的总权重最多为 W。(你不必构建项目的实际子集。)你的算法的运行时间，应该是最大项目值 vmax = max vi 和项目数 n 的多项式。

Answer 1

我认为这样做是不可能的。如果将所有权重乘以某个小于 1 的值，您希望算法运行得比以前更快。但这是不可能的，因为问题实际上并没有改变。