## An overview of the

Given a set of items, each item has its own weight and value, the existing backpack, can bear a limited weight, in the restricted weight, take a number of items, making the total value of the maximum. This kind of problem is called the backpack problem.

## 01 Backpack Problem

Currently there are N items and a backpack of volume V. We know that the volume of item I is c_i, and the value is w_i. Since there is only one item of each kind, we can only choose to put it or not, which is called the 01 backpack problem. Now you need to pick a number of items that add up to as much value as possible, as long as they don’t add up to more than V. 1. Define the status DP [I][J]: the maximum value of the first I item, if the weight does not exceed J 2. Write the state transition equation: 3. coding!

```
memset(dp, 0.sizeof(dp)); / / initialization
for(int i = 1; i <= N; i++)
for(int j = 0; j <= V; j++){ // Make sure the boundary starts at 0
if(j >= c[i])
dp[i][j] = max(dp[i - 1][j - c[i]] + w[i], dp[i - 1][j]);
else
dp[i][j] = dp[i - 1][j];
}
Copy the code
```

Time complexity: O(NV)

#### The optimization of knapsack problem

It’s hard to optimize in time, but there’s a lot of double counting in space. Carefully observe the above state transition equation, for DP [I][j], only dp[i-1] layer is needed, and since it is [j-c[I]], we can know that we need to use a certain dp on the left continuously, starting from this property. Using a one-dimensional array DP [J] to represent the maximum value when the current weight does not exceed J, the state transition equation can be obtained

For (int I = 1; i <= n; ++i) for (int j = v; j >= c[i]; –j) dp[j] = max(dp[j – c[i]] + w[i], dp[j]);

## Multiple backpack problem

There are N items, the ith item has a volume of C [I] and a value of w[I], and each item has a finite number of N [I]. For the existing backpack with a capacity of V, please put a number of items into it and make the total value as large as possible under the condition that the total volume does not exceed V.

Conversion 01 Backpack:N [I] items are split in turn and converted into 01 knapsack problem solution with time complexity of O(V ∑n). The transfer equation is as follows

The code is as follows:

```
for (int i = 1; i <= N; i++)
for (int j = 0; j <= V; j++)
for (int k = 0; k <= n[i]; k++)
if (j >= c[i] * k)
dp[i][j] = max(dp[i - 1][j - c[i] * k] + w[i] * k, dp[i][j]);
If k=0, dp[I -1][j] =0, dp[I -1][j] =0
Copy the code
```

#### Spatially optimized version

```
for (int i = 1; i <= N; i++)
for (int j = V; j >= 0; j--)
for (int k = 0; k <= n[i]; k++)
if (j >= c[i] * k)
dp[j] = max(dp[j - c[i] * k] + w[i] * k, dp[j]);
Copy the code
```

#### Binary optimized version:

Using 1, 2, 4, 8, 16 can form any integer from 1 to 63. Taking advantage of this property, assuming that the ith item has n[I] items, we divide it into groups of 1, 2, 4, 8… 2^(k-1), n[I]-2^k+1, where k is the largest integer where n[I]-2^k+1 > 0. It can be proved that any number from 1 to N can be formed by the combination of several groups. So instead of the enumeration from 0 to n[I], the complexity of the enumeration is reduced to O(V sigma logn).

```
// Find the maximum k
int ncnt = 1;
for(int i = 1; i <= N; ++i){
int k;
for(k = 1; n[i]-(1<<k)+1 > 0; ++k){
nc[ncnt] = (1<<(k- 1))*c[i];
nw[ncnt] = (1<<(k- 1))*w[i];
++ncnt;
}
// Check if there are any left
--k;
nc[ncnt] = (n[i]-(1<<k)+1)*c[i];
nw[ncnt] = (n[i]-(1<<k)+1)*w[i];
++ncnt;
}
/ / 01 knapsack
for(int i = 1; i <= ncnt; ++i){
for(int j = V; j >= nc[i]; --j){
dp[j] = max(dp[j], dp[j-nc[i]]+nw[i]); }}Copy the code
```

## Complete backpack problem

Currently there are N kinds of items. The ith kind of item has a volume of C [I] and a value of w[I]. The number of each item is unlimited and you can choose any number of items. For the existing backpack with a capacity of V, please put some items into it so that the total volume does not exceed V and the total value is as large as possible. This is the problem with the full backpack, the difference between the 01 backpack and the infinite number of items.

#### Convert to 01 knapsack solution:

```
for (int i = 1; i <= N; i++)
for (int j = 0; j <= V; j++)
for (int k = 0; k * c[i] <= j; k++)
dp[i][j] = max(dp[i - 1][j - c[i] * k] + w[i] * k, dp[i][j]);
Copy the code
```

#### Time optimization algorithm:

In fact, since the number of each item is infinite, we don’t need to worry about the problem of dp[I][j-c[I]] being updated any more, because it is updated immediately, we can put the corresponding number in the next round

01 knapsack with difference only lies in the dp [I] [j – c [I]] and dp [I – 1] [j – c [I]] (01 knapsack), the time complexity O (NV)

```
for (int i = 1; i <= n; i++)
for (int j = 0; j <= v; j++) {
if (j >= c[i])
dp[i][j] = max(dp[i][j - c[i]] + w[i], dp[i - 1][j]);
else
dp[i][j] = dp[i - 1][j];
}
Copy the code
```

#### Spatial optimization:

```
for (int i = 1; i <= n; i++)
for (int j = c[i]; j <= v; j++){
dp[j] = max(dp[j], dp[j-c[i]]+w[i]);
Copy the code
```

It can be seen that at the end of the optimization, there is only a difference in order with 01 backpack

## subtotal

An interesting detail of the knapsack problem: after optimization to one dimension, if the initial DP [1-n] is all 0, the final DP [I] means that the total weight does not exceed the maximum value of M; If only dp[0] is initialized to 0 and the rest is -INF, then dp[I] means the maximum value when the total weight is exactly I