01 Backpack Problem
- 1. 【Template】01 Backpack
- 2. Split equal-sum subsets
- 3. Objectives and
- 4. The weight of the last stone II
01 The knapsack problem is a dynamic programming problem that is used to solve the combination of items with the greatest value in a limited-capacity knapsack. Specific steps are as follows:
- Define a two-dimensional array dp[i][j] to represent the maximum value that can be obtained by selecting several items from the previous i items and putting them into a backpack with a capacity of j.
- Initialize dp[0][j] and dp[i][0] to 0, which means that when there are no items or backpack capacity, the value is 0. Traverse each item and each backpack capacity, and update dp[i][j] based on the weight and value of the item. There are two situations: 1. If the weight of item i is greater than the backpack capacity j, then it cannot be put in,
dp[i][j] = dp[i-1][j], which is equal to the maximum value of the first i-1 items. 2. If the weight of item i is less than or equal to the backpack capacity j, you can choose to put it in or not,dp[i][j] = max(dp[i-1][j], dp[i- 1][j-w[i]] + v[i]), that is, take the larger value between putting in and not putting in. - Finally, dp[n][V] is returned, which is the maximum value of the first n items put into the backpack with capacity V.
Two-dimensional tables and DP arrays both play important roles in the knapsack problem, but their respective roles are different.
Two-dimensional table: In the knapsack problem, we usually use a two-dimensional table to record the solutions to the subproblems. The size of a two-dimensional table is usually (m + 1) × (W + 1), where m is the number of items and W is the capacity of the backpack. Each cell represents the maximum value that can be obtained for a given capacity and set of items. By filling this two-dimensional table, we can get the optimal solution to the knapsack problem.
DP array: The DP array is the core part of the knapsack problem. It is used to store the optimal solution for each state. DP[i][j] represents the maximum value that can be obtained when there are only the first i items and the backpack capacity is j. By filling the DP array, we can get the optimal solution to the knapsack problem.
In general, the two-dimensional table can be regarded as a “map” of the DP array, which tells us how to fill the DP array to get the optimal solution. The DP array is where the optimal solution is actually calculated.
1. 【Template】01 Backpack
1. Question link: [Template] 01 Backpack
2.Title description:
You have a backpack, the maximum volume it can hold is V. Now there are n items, the i-th item has a volume of vi and a value of wi.
(1) What is the maximum value of items that this backpack can hold?
(2) If the backpack is exactly full, what is the maximum value of items it can hold?
Enter description:
The two integers n and V in the first line represent the number of items and the volume of the backpack.
The next n lines have two numbers vi and wi in each line, representing the volume and value of the i-th item.
1≤n,V,vi,wi ≤1000.
Output description:
The output has two lines. The first line outputs the answer to the first question, and the second line outputs the answer to the second question. If there is no solution, please output 0.
Example 1
enter:
3 5
2 10
4 5
1 4
Output: 14 9
Explanation: The total value is the largest when the first and third items are loaded, but the second and third items can make the backpack exactly full and the total value is the largest.
Example 2
enter:
3 8
12 6
11 8
6 8
Output: 8 0
Explanation: When loading the third item, the total value is the largest but not satisfactory. There is no solution to filling the backpack.
3. Problem analysis: The above question roughly means that each item has a volume Vi and a value Wi. Now there is a backpack with a volume V, so two one-dimensional arrays need to be used to manage the volume and value of the items, and then find (1) What is the maximum value of items that this backpack can hold? (2) If the backpack is exactly full, what is the maximum value of items it can hold? Then the state is represented according to the above solution. The dp[i][j] represents the maximum value that can be obtained by selecting several items from the previous i items and putting them into a backpack with a capacity of j. That is, imagine a two-dimensional table in your mind. The abscissa of the table represents the capacity V of the backpack, and the ordinate represents the total value W of the items in the backpack.
- State representation: dp[i][j] represents the maximum value that can be obtained by selecting several items from the previous i items and putting them into a backpack with a capacity of j.
- State transition equation: (1) Find the maximum value of items that this backpack can hold? For each item, there are only two results: selected and not selected. To select, you need to first determine whether the capacity of the backpack is sufficient, so you can first process the item and not select it. If not, then
dp[i ][j] = dp[i-1][j]; if selected, it means that the capacity of the backpack can be greater than the volume of the item, that is, j – v[i] >= 0, after selecting the item , and select the largest value among the first few items selected in (i-1), (If you want to understand this better, it is recommended to draw a dp array) That is,dp [i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]). (2) If the backpack is exactly full, what is the maximum value of items it can hold? What if the backpack happens to be full, then just add conditions. For the dp table asked in the first question, you can set the position where the backpack is not full to -1. If a certain position in the dp table is -1, then just leave it unchecked. . - Initialization: Because to find the value of i, j position, you need to know the value of i – 1, j – w[i] position. Based on past experience, you can set one more row and one column to prevent out-of-bounds access. For the first question, the dp position of items that cannot be installed is set to 0, so all are initialized to 0. For the Second question, the not full position is set to -1, so it needs to be broken down: the first row of the dp table represents the individual number of the backpack. The number is 0–n, and the volume of the item is 0, so except for the 0,0 position, which is just full, the rest is not full, that is, except for the 0,0 position, which is 0, the other positions are initialized to -1; the first column of the dp table It means that the volume of the item is 0, and the number of backpacks is 0-n, so all are initialized to 0.
- Order of filling in the form: from left to right and from top to bottom.
- Return value: Returns the value at the position of dp[n][v]. The second question is that dp[n][v] may be -1, so judge it here. If it is -1, return 0.
4. The code is as follows:
#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[N][N];
int main()
{<!-- -->
cin >> n >> V;
for (int i = 1; i <= n; + + i)
cin >> v[i] >> w[i];
for (int i = 1; i <= n; + + i)
{<!-- -->
for (int j = 1; j <= V; + + j)
{<!-- -->
dp[i][j] = dp[i - 1][j];
if (j >= v[i])
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
}
}
cout << dp[n][V] << endl;
memset(dp, 0, sizeof dp); // Clear the dp table
for (int j = 1; j <= V; + + j)
dp[0][j] = -1;
for (int i = 1; i <= n; + + i)
{<!-- -->
for (int j = 1; j <= V; + + j)
{<!-- -->
dp[i][j] = dp[i - 1][j];
if (j >= v[i] & amp; & amp; dp[i - 1][j - v[i]] != -1)
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
}
}
cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
return 0;
}
2. Split equal-sum subsets
1. Question link: Split equal sum subsets
2.Title description:
You are given a non-empty array nums containing only positive integers. Please determine whether this array can be divided into two subsets so that the sum of the elements of the two subsets is equal.
Example 1:
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be split into [1, 5, 5] and [11].
Example 2:
Input: nums = [1,2,3,5]
Output: false
Explanation: An array cannot be split into two elements and equal subsets.
hint:
1 <= nums.length <= 200
1 <= nums[i] <= 100
3. Question analysis: This question is to divide an array into two subsets so that the sum of the elements of the two subsets is equal. You can convert it like this, sum the array, and then divide it by 2 to find the sum of the two subsets of the array. The next step is to select some numbers in the nums array so that the sum of these selected numbers is exactly equal to the sum of the array. half. In this way, this question is a 01 knapsack problem.
- State representation: dp[i][j] means selecting certain values among the first i numbers, and the sum of these numbers is exactly j.
- State transition equation: For the number of i and j positions in the dp table, there may be two results: selected and not selected. If not selected, then
dp[i][j] = dp[i - 1][ j]; If you choose, you need to judge whether the remaining space in the backpack is enough to choose this number. This number is at the i-th position, has j spaces, and has a volume of nums[i], that is, j > nums[ i], thendp[i][j] = max(dp[i][j], dp[i - 1][j - nums[i]]); - Initialization: Same as the second question above, no explanation will be given.
- Order of filling in the form: from left to right and from top to bottom.
- Return value: If dp[n][v]=-1, return false, otherwise return true.
4. The code is as follows:
class Solution
{<!-- -->
public:
bool canPartition(vector<int> & nums)
{<!-- -->
int n = nums.size();
int sum = 0;
for (auto & x : nums)
sum + = x;
if (sum % 2 == 1)
return false;
int v = sum / 2;
vector<vector<int>> dp(n + 1, vector<int>(v + 1));
for (int j = 1; j <= v; + + j) // initialization
dp[0][j] = -1;
for (int i = 1; i <= n; + + i)
{<!-- -->
for (int j = 1; j <= v; + + j)
{<!-- -->
dp[i][j] = dp[i - 1][j];
if (j >= nums[i - 1] & amp; & amp; dp[i - 1][j - nums[i - 1]] != -1) // nums[i - 1] is because of the increase One row and one column, nums should correspond to the relationship of dp, so i-1
dp[i][j] = max(dp[i][j], dp[i - 1][j - nums[i - 1]]);
}
}
if (dp[n][v] != -1)
return true;
else
return false;
}
};
3. Goals and
1. Question link: target and
2.Title description:
You are given an array of non-negative integers nums and an integer target .
By adding +’ or -’ before each integer in the array, and then concatenating all the integers, you can construct an expression:
For example, nums = [2, 1], you can add +’ before 2 and -’ before 1, and then concatenate them to get the expression “+ 2-1”.
Returns the difference that can be constructed by the above method and the result is equal to target.
Example 1:
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to make the final goal sum equal to 3.
-1 + 1 + 1 + 1 + 1 = 3
+ 1 – 1 + 1 + 1 + 1 = 3
+ 1 + 1 – 1 + 1 + 1 = 3
+ 1 + 1 + 1 – 1 + 1 = 3
+ 1 + 1 + 1 + 1 – 1 = 3
Example 2:
Input: nums = [1], target = 1
Output: 1
hint:
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
3. Problem analysis: We need to add positive and negative signs to the numbers in the array so that their sum is equal to the given target. For each number, there are positive and negative signs. Then for each additional number, there will be 2^n more. It is possible, so it is not easy to solve it violently. But we regard the positive and negative numbers in nums as parts respectively, and set them as a and b, then a + b = sum; a – b = target, we can calculate a = (sum + target) / 2, then is it It can be seen as finding some numbers in the nums array so that the sum of these numbers is a (that is, a number with a positive sign), so this question is basically the same as the previous question.
- State table?: dp[i][j] Table?: Select among the first i numbers, the sum is exactly equal to j,? How many choices are there?
- State transfer process: According to the elements at the last position, there are two strategies to select the last element or not to select the last element: 1. Do not select nums[i]: dp[i][j] = dp[i – 1][j]; 2. Select nums[i]: In this case, there are preconditions. At this time, nums[i] should be equal to j. Because if this element all makes up the sum, there is no point in choosing it. Then the number of cases that we can make up with a total sum of j depends on whether we can make a total of j – nums[i] by selecting the first i – 1 elements. According to the state table?, at this time dp[i][j] = dp[i – 1][j – nums[i]].
- Initialization: Since you need to access the data of the previous step, you can initialize the third step first. The third table does not select any elements, and must make up the index and j. Only 0,0 meets the requirements, so the th element only needs to be initialized dp[0][0] = 1.
- Order of filling in the form:
According to the “state transfer process”, we need to fill in each link “from top to bottom”, and the order of each link is “so-called”. - Return value: Returns the value of dp[n][a]. Among them, n represents the index of the array, and a represents the index sum to be assembled.
4. The code is as follows:
class Solution
{<!-- -->
public:
int findTargetSumWays(vector<int> & amp; nums, int target)
{<!-- -->
int n = nums.size();
int sum = 0;
for (auto & x : nums)
sum + = x;
int v = (sum + target) / 2;
if (v < 0 || (sum + target) % 2)
return 0;
vector<vector<int>> dp(n + 1, vector<int>(v + 1));
dp[0][0] = 1;
for(int i = 1; i <= n; i + + ) // Fill in the form
for(int j = 0; j <= v; j + + )
{<!-- -->
dp[i][j] = dp[i - 1][j];
if(j >= nums[i - 1])
dp[i][j] + = dp[i - 1][j - nums[i - 1]];
}
//return results
return dp[n][v];
}
};
4. The weight of the last stone II
1. Question link: The weight of the last stone II
2.Title description:
There is a pile of stones, represented by an array of integers called stones. where stones[i] represents the weight of the i-th stone.
Each round, pick any two rocks and smash them together. Suppose the weights of the stones are x and y, and x <= y. Then the possible results of crushing are as follows:
If x == y, then both rocks will be completely crushed;
If x != y, then the stone of weight x will completely shatter, and the stone of weight y will have a new weight of y-x.
In the end, at most there will be only one stone left. Returns the smallest possible weight of this stone. If there are no stones left, 0 is returned.
Example 1:
Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation: Combining 2 and 4, you get 2, so the array is converted to [2,7,1,8,1]. Combining 7 and 8, you get 1, so the array is converted to [2,1,1,1], combination 2 And 1, you get 1, so the array is converted to [1,1,1]. Combining 1 and 1, you get 0, so the array is converted to [1], which is the optimal value.
Example 2:
Input: stones = [31,26,33,21,40]
Output: 5
hint:
1 <= stones.length <= 30
1 <= stones[i] <= 100
3. Problem analysis: To crush stones in pairs, crushing them in pairs means finding two numbers and subtracting them. The subtracted numbers are regarded as two parts. The sum is recorded as the sum of all the numbers. To make the two parts of the numbers As equal as possible, then is it possible to find some numbers among all the numbers so that their sum is close to half of sum? In this way, it can be regarded as having a backpack with a capacity of sum / 2, and filling sum as much as possible That’s it.
4. The code is as follows:
class Solution
{<!-- -->
public:
int lastStoneWeightII(vector<int> & amp; stones)
{<!-- -->
int n = stones.size();
int sum = 0;
for (auto & x : stones)
sum + = x;
int v = sum / 2;
vector<vector<int>> dp(n + 1, vector<int>(v + 1));
for (int i = 1; i <= n; + + i)
{<!-- -->
for (int j = 0; j <= v; + + j)
{<!-- -->
dp[i][j] = dp[i - 1][j];
if (j >= stones[i - 1])
dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
}
}
return sum - 2 * dp[n][v];
}
};