背包使用动态规划

Question

有一种使用动态规划求解背包问题的通用算法。但是对于W=750000000是不行的，因为有bad alloc的错误。有什么想法可以根据我的 W 值解决这个问题吗？

int n=this->items.size();
std::vector<std::vector<uint64_t>> dps(this->W + 1, std::vector<uint64_t>(n + 1, 0));
for (int j = 1; j <= n; j++)
    for (int k = 1; k <= this->W; k++) {
        if (this->items[j - 1]->wts <= k)
            dps[k][j] = std::max(dps[k][j - 1], dps[k - this->items[j - 1]->wts][j - 1] + this->items[j - 1]->cost);
        else
            dps[k][j] = dps[k][j - 1];
    }

Answer 1

你没有显示 n，但即使我们假设它是 1，让我们看看你试图分配多少数据。所以，它将是：

W*64*2 // Here we don't consider overhead of the vector

结果是：

750000000*64*2 bits = ~11.1758Gb

我猜这比 space 您的程序允许的要多。你将需要采取一种新的方法。也许尝试将问题作为多个块来处理。上半场和下半场分开考虑，然后交换。

Answer 2

首先，你可以只用一维来解决背包问题。这会将您的内存从 dp[W][n] (n*W space) 减少到 dp[W] (W space)。你可以看这里：0/1 Knapsack Dynamic Programming Optimazion, from 2D matrix to 1D matrix

但是，即使你只使用dp[W]，你的W也确实很高，而且可能占用太多内存。如果您的物品很大，您可以使用一些方法来减少可能的重量数量。首先，意识到你不需要 W 的所有位置，只需要那些 weight[i] 之和存在的位置。

例如：

W = 500
weights = [100, 200, 400]

您永远不会使用矩阵的位置 dp[473]，因为项目只能占据位置 p = [0, 100, 200, 300, 400, 500]。很容易看出这个问题和when:

一样

W = 5
weights = [1,2,4]

另一个更复杂的例子：

W = 20
weights = [5, 7, 8]

使用与之前相同的方法，您不需要从 0 到 20 的所有权重，因为项目只能占据位置

p = [0, 5, 7, 5 + 7, 5 + 8, 7 + 8, 5 + 7 + 8]
p = [0, 5, 7, 12, 13, 15, 20]

，您可以将矩阵从 dp[20] 减少到 dp[p 的大小] = M[7]。

背包使用动态规划

Knapsack using dynamic programming

c++

algorithm

knapsack-problem