# 【 Backpack problem series 】 a classic backpack problem

This series is based on the study of Gongshui Sanye’s big wechat public number – backpack problem after sorting out, if there is any violation, please inform us

A path to learning at 🐔

## Classic backpack problem

### [B].

``There are values. Length items and a backpack with a capacity of N. There is one and only one of each item. The weights are **weights[I]**, and the values are **values[I]**. Solve which items to put into the backpack so that the total volume of these items does not exceed the backpack capacity, and the total value of the maximum. Example 1: Input: V = 4, values = [4,2,3], weights = [4,2,3] Output: 4 Explanation: Select only the first item to maximize the value. Example 2: input: V = 5, values = [4,2,3], weights = [4,2,3] output: 5 explanation: do not select the first item, select the second and third items to maximize the value.Copy the code``

## [D].

• So when we’re dealing with dp problems and we can’t think of the DP equation directly at first, we can think of DFS recursion to determine the recursive equation

• Int DFS (int n,int I,int [] values, int[] weights)

• N (current capacity), I (current item)

• Therefore, the DP equation can be generated by two variable parameters

• Dp [I][j] represents the highest value obtained for I items at maximum weight J before use

• When I = 0, we need to initialize dp array dp[0][j]

• The derivation of dynamic equation can be analyzed according to the following ideas

• Face value whether I, need to decide to take * * (dp [I] [j – weight [I]] + val [I]) * * or don’t take (dp) [j] [I – 1] whose value is higher

• ``````dp[i][j] = Math.max(dp[i-1][j],dp[i][j-weights[i]] + values[i])
Copy the code``````
``````public int getMaxValue(int[] value, int[] weights, int n) {
int[][] dp = new int[value.length][n + 1];
// Boundary conditions
for (int i = 0; i < n; i++) {
dp[0][i] = (weights[0] <= i) ? value[0] : 0;
}
for (int i = 1; i < value.length; i++) {
int val = value[i];
for (int j = 1; j <= n; j++) {
if (j >= weights[i]) {
// Select and deselect the maximum value of the current item
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + val); }}}return dp[value.length - 1][n];
}
Copy the code``````

Time complexity O(N*C) N represents the number of items and C represents the maximum weight

Optimization 1: a combination of scrolling arrays and dynamic programming optimizes storage space

• According to the above recursive equation, it can be seen that DP [I][j] is only related to DP [i-1][j]. Such a dynamic programming problem can be solved by rolling the array dp equation
• Define **dp[2][j]** to store the previous bit’s maximum value solution and the current bit’s maximum value solution
• How do we traverse two elements we can translate traverse by parity
`````` public int getMaxValue(int[] values, int[] weights, int n) {
int[][] dp = new int[2][n + 1];
for (int i = 0; i < n; i++) {
dp[0][i] = (weights[0] <= i) ? values[0] : 0;
}
for (int i = 1; i < values.length; i++) {
for (int j = 0; j <= n; j++) {
// Do not select the current item
int tempF = dp[(i - 1) & 1][j];
// Select the current item
int tempT = j >= weights[i] ? dp[(i - 1) & 1][j - weights[i]] + values[i] : 0;
dp[i & 1][j] = Math.max(tempF, tempT); }}return dp[(values.length - 1) & 1][n];
}
Copy the code``````

Time complexity O(N*C) N represents the number of items and C represents the maximum weight

Optimization two: clear dependence, space optimization again

• Based on the above optimization, you can see that the current maximum value is related to only two determined values
• Is the dp [I] [j] only dp [j] and [I – 1] * * dp [I] [j – weights [I]] * * two values
``````public int getMaxValue(int[] values, int[] weights, int n) {
int[] dp = new int[n + 1];
for (int i = 0; i < values.length; i++) {
for (int j = n; j >= weights[i]; j--) {
// do not select this item
int x = dp[j];
// Select this item
inty = dp[j - weights[i]] + values[i]; dp[j] = Math.max(x, y); }}return dp[n];
}
Copy the code``````