这是一个古老而著名的背包问题:
这里我有一个约束的背包问题。
我有大小为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,则项目的最大值是有限的。
所以,现在我想知道,在这种情况下,如何降低算法的时间复杂度?我认为背包问题取决于背包的大小和项目的数量,那么项的值如何改变我的算法?
有没有人能帮我提高这个背包算法的时间复杂度,我已经用滑动数组来提高空间复杂度了。
问题如下:
给定大小为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
我很难用背包来解决背包问题。
例如,对于以下值,背包函数将返回14作为解决方案,但正确的结果应该是7。
int n = 3, weights[] = {2, 3, 1}, values[] = {6, 15, 7};
int solution = 0, max = 2;
void Knapsack (int i, int max, int value, int *solution)
{
int k;
for (k = i; k < n; k++) {
if (weights[k] <= max) {
Knapsack (k, max - weig