这是一个古老而著名的背包问题:
这里我有一个约束的背包问题。
我有大小为W = 100000000和N = 100的背包,我为其编写了动态解决方案,我的算法的复杂性是O(100000000*100),这在时间和空间上都太大了,但是这里有一个条件,即无论是W ≤ 50000 or max 1≤ i ≤ n Vi ≤ 500.还是W ≤ 50000 or max 1≤ i ≤ n Vi ≤ 500.,所以如果背包大小超过50000,则项目的最大值是有限的。
所以,现在我想知道,在这种情况下,如何降低算法的时间复杂度?我认为背包问题取决于背包的大小和项目的数量,那么项的值如何改变我的算法?
我正在尝试使用非整数值来减少背包DP算法所需的时间和空间。
In particular, if the [elements] are nonnegative but not integers, we could
still use the dynamic programming algorithm by scaling and rounding (i.e. using
fixed-point arithmetic), but if the problem requires fractional digits of
precision to arrive at the correct
有没有人能帮我提高这个背包算法的时间复杂度,我已经用滑动数组来提高空间复杂度了。
问题如下:
给定大小为n的A[i]项,整数m表示背包的大小。这个背包你能装满多少?
如果我们有4个大小为[2, 3, 5, 7]的项目,而背包大小为11,我们可以选择[2, 3, 5],这样这个背包的最大大小是10。如果背包大小为12,我们可以选择[2, 3, 7]并完全填充它。
函数应该返回我们可以在给定的背包中填写的最大大小。
class Solution:
# @param m: An integer m denotes the size of a backpack
# @param A: Given n