John - 3 years ago 242
C++ Question

# Knapsack using dynamic programming

There is a common algorithm for solving the knapsack problem using dynamic programming. But it's not work for W=750000000, because there is an error of bad alloc. Any ideas how to solve this problem for my value of 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];
}
``````

First of all, you can use only one dimension to solve the knapsack problem. This will reduce your memory from dp[W][n] (n*W space) to dp[W] (W space). You can look here: 0/1 Knapsack Dynamic Programming Optimazion, from 2D matrix to 1D matrix

But, even if you use only dp[W], your W is really high, and might be too much memory. If your items are big, you can use some approach to reduce the number of possible weights. First, realize that you don't need all positions of W, only those such that the sum of weight[i] exists.

For example:

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

You will never use position dp[473] of your matrix, because the items can occupy only positions `p = [0, 100, 200, 300, 400, 500]`. It is easy to see that this problem is the same as when:

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

Another more complicated example:

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

Using the same approach as before, you don't need all weights from 0 to 20, because the items can occupy only fill up to positions

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

, and you can reduce your matrix from dp[20] to dp[size of p] = M[7].

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download