1, Basic dynamic programming
Like greedy algorithm, in dynamic programming, the solution of a problem can be regarded as the result of a series of decisions. The difference is that in the greedy algorithm, an irrevocable decision is made every time the greedy criterion is used, while in dynamic programming, it is also necessary to investigate whether each optimal decision sequence contains an optimal subsequence. When a problem has an optimal substructure, we will think of using dynamic programming to solve it. Although some problems have the simplest and effective methods, as long as we always make the best choice at present.
The choice of greedy algorithm can depend on the choice made in the past, but it will never depend on the future choice or the solution of the subproblem, which makes it have a certain speed advantage. To solve the dynamic programming problem, we should first determine the subproblem and judge which variables are related to the scale of the problem. Secondly, we should determine the state and deduce the state transition equation.
In the dynamic programming problem, the state transition equation is the core. We should judge whether it meets all the conditions and deal with the boundary problem well. 2, Knapsack problem 1.01 knapsack 01 knapsack is to take out several knapsacks from M items and put them in space W. the volume of each object is W1,W2,... Wn, and the corresponding value is P1, P2,... Pn.
1.01 Backpack
Is the simplest problem in backpacking. 01 the constraint condition of knapsack is that given several items, each item has and only one, and has two attributes: weight and volume. In the 01 knapsack problem, because there is only one item of each kind, we only need to consider the choice and non choice of each problem. If you don't choose to put it into the backpack, you don't need to deal with it. If you choose to put it into the backpack, because you don't know how much space the previously collected items occupy, you need to enumerate all the situations that may occupy the backpack space after putting this item into the backpack.
2.01 backpack example
Example 1: there are four items. The total capacity of the thief's backpack is 8. How can you steal the most valuable items? For example: Item No.: 1 2 3 4 item weight: 2 3 4 5 item value: 3 4 5 8 records f(k,w): when the backpack capacity is w, the existing K items can be stolen, and the maximum value can be stolen
1. #include<cstdio>
2. #include <iostream>
3. #include<cstdlib>
4. #include<algorithm>
5. #include <cstring>
6. using namespace std;
7. int f[5][9] = {0};
8. int w[5] ={0,2,3,4,5};
9. int v[5] ={0,3,4,5,8};
10. int main(){
11. int i,j;
12. memset(f,0,sizeof(f));
13. for(int i = 1; i < 5; i++){
14. for(int j = 1; j < 9; j++){
15. if(w[i] > j){
16. f[i][j] = f[i - 1][j];
17. }else{
18. f[i][j] = max(f[i - 1][j],f[i - 1][j - w[i]] + v[i]);
19. }
20. }
21. }
22. for(int i = 0; i < 5; i++){
23. for(int j = 0; j < 9; j++){
24. cout <<"f["<< i << "]" <<"[" << j<<"]= " << f[i][j] << endl;
25. }
26. }
27.
28. }
3.01 backpack space optimization
Rolling array: according to the post invalidity principle, the next state is only related to the previous state and can be compressed into a one-dimensional array. Refresh the dp array every time you run it; Note that the new dp array must be inverted, and the remaining capacity of the backpack should start from the maximum capacity, otherwise the small capacity of the object will be covered by the small capacity value of the item. For example, dp[8] = max(dp[8],dp[4] + 6) at this time, the dp[4] of this layer has not been updated, and it can be used directly. If you are pushing, dp[4] has been covered as this layer at this time, so it is impossible to correctly calculate the following;
Chenchen is a gifted and intelligent child. His dream is to become the greatest doctor in the world. To this end, he wanted to worship the most prestigious doctor nearby as a teacher. The doctor gave him a difficult problem in order to judge his qualifications. The doctor took him to a cave full of herbs and said to him: "Child, there are some different herbs in this cave. It takes some time to pick each one, and each one has its own value. I will give you a period of time, during which you can pick some herbs. If you are a smart child, you should be able to maximize the total value of the herbs you pick."
Input format
The first line has 22 integers TT (1 \le T \le 10001 ≤ T ≤ 1000) and MM (1 \le M \le 1001 ≤ M ≤ 100), separated by a space. TT represents the total time that can be used to collect herbs, and MM represents the number of herbs in the cave.
The next MM line includes two integers between 11 and 100100 (including 11 and 100100), representing the time of picking a herb and the value of the herb respectively.
Output format
Output the maximum total value of herbs that can be collected within a specified time.
If you are Chenchen, can you finish this task?
1). Dynamic programming without compression
#include<iostream>
#include<algorithm>
using namespace std;
const int n = 10001;
int dp[n][n];
int t[n];
int v[n];
int main(){
int T,m,i,j;
cin >> T >> m;
for(i = 1; i <= m; i++){
cin >> t[i] >> v[i];
}
for(i = 1; i <= m; i++){
for(j = 1; j <= T; j++){
if(t[i] > j){
dp[i][j] = dp[i - 1][j];
}else{
dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - t[i]] + v[i]);
}
}
}
cout << dp[m][T];
}
2). Dynamic programming after compression (using rolling array)
#include<bits/stdc++.h>
using namespace std;
const int n = 10001;
int dp[n];
int t[n];
int v[n];
int main(){
int T,m;
cin >> T >>m;
for(int i = 1; i <= m; i++){
cin >> t[i] >> v[i];
}
for(int i = 1; i <= m; i++){
for(int j = T; j >= 1; j--){ //Recursion j must loop backwards, or it will be overwritten
if(j >= t[i]){
dp[j] = max(dp[j],dp[j - t[i]] + v[i]);
}
}
}
cout << dp[T];
}
Example 2: many years ago, in Teddy's hometown, there was a man called an ancient collector. He liked to collect different bones. This person has a big bag (the volume of the bag is V) and many collected bones. Obviously, different bones have different values and different volumes. Now considering the value of each bone and his bag, please calculate the maximum total value of the bones that this person can collect?
Input:
Start to input a number T, which means there are t groups of test data. Each test data starts with two numbers, N and v, representing the total number of bones and the volume of the bag. Enter n numbers in the next line to represent the value of N bones. Enter n numbers in the last line to represent the volume of N bones.
Output:
Output a number for each test data, indicating the maximum value. Sample input: 15 101 2 3 4 55 4 3 2 1 sample output 14
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int n = 1000;
int dp[n][n];
int val[n];
int vo[n];
int main()
{
int t;
cin >> t;
while (t--)
{
int n, v;
memset(dp, 0, sizeof(dp));
cin >> n >> v;
for (int i = 1; i <= n; i++)
{
cin >> val[i];
}
for (int i = 1; i <= n; i++)
{
cin >> vo[i];
}
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= v; j++)
{
if (vo[i] > j)
{
dp[i][j] = dp[i - 1][j]; //can't let go
}
else
{
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vo[i]] + val[i]); //Total value of the i-th item after putting it into the backpack
}
}
}
cout << dp[n][v] << endl;
}
}
3, Coin problem
There are several coins with face values of 1, 5, 10, 20 and 50.100 respectively. How many coins are needed to round up the value of w.
For example, w= 15, according to greedy thinking: we choose the coin with the largest face value to try every time. 15 = 1*11 + 4 * 1； At least five coins are needed, but actually three coins with a face value of 5 are needed
Scheme 1) greedy thinking and short-sighted situation
2) Violent enumeration, too complex
3) DP when we want to round up a coin with a value of 15, we face three situations. When we take a coin with a value of 1, we will face a coin with a value of 14. When we take a coin with a value of 5, we will face a coin with a value of 10. When we take a coin with a value of 11, we will face a coin with a value of 4. The minimum number of coins required to round up a value n is f(n)
Principle: f(n) is only related to f(n-1),f(n-5),f(n-11). f(n) = min {1 + F (n-1), 1 + F (N-5), 1 + F (N-11)}
Conclusion: the optimal solution of the large problem of the optimal substructure can be deduced from the optimal solution of the small problem. There is no aftereffect. Once f(n) is determined, you can call its value directly. Don't care about the calculation process of f(n)
#include<bits/stdc++.h>
using namespace std;
int min(int a,int b){
return a <b ?a:b;
}
int main(){
int dp[100],i;
dp[0] = 0;
int cost;
for(int i = 1; i <= 15; i++){
cost = 0x3f3f3f3f;
if(i - 1 >= 0) cost = min(cost,dp[i - 1] + 1);
if(i - 5 >= 0) cost = min(cost,dp[i - 5] + 1);
if(i - 11 >= 0) cost = min(cost,dp[i - 11] + 1);
dp[i] = cost;
cout <<"dp[" <<i <<"] = " <<" "<< dp[i]<<endl;
}
}
3, Longest ascending subsequence (LIS)
The longest ascending subsequence is given a sequence of length n, and a subsequence is selected from it. This subsequence needs to increase monotonically. Ask the length of the longest ascending subsequence.
For example: the longest ascending subsequence of 1 52 3 11 7 9 is: 1 2 3 7 9 remember that f(x) is the length of Lis ending with a[x], so LIS = max{f(x)}
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int dp[N];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
dp[i] = 1;
for (int j = 1; j < i; j++)
{
if (a[j] < a[i])
{
dp[i] = max(dp[i], dp[j] + 1);
}
}
cout << i << " " << dp[i] << endl;
}
}
Example: give an array with length N, and each number in the array is between - 1000 and 1000. Find the maximum continuous interval sum of this array.
For example (6, - 1, 5, 4, - 7), then the maximum sum of continuous intervals in this array is 14
Input:
Input t in the first line, indicating T group of data. The beginning of each group of data is an integer n, indicating the length of the array. Next, there are n numbers, representing the N numbers of this array
Output:
For each group of data, the maximum continuous interval sum is output, the start position and end position are given, and the state transition equation is dp[i] = max(dp[i],a[i])
#include<iostream>
using namespace std;
int const N = 1e6 + 10;
int dp[N];
int arr[N];
int main(){
int t;
cin >> t;
while(t--){
int n;int begin ,end ,pos = 1;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> arr[i];
}
dp[1] = arr[1];
int maxn = -0x3f3f3f3f;
for(int i = 1; i <= n; i++){
if(dp[i - 1] + arr[i] >= arr[i]){
dp[i] = dp[i - 1] +arr[i];
} else{
dp[i] = arr[i];
pos = i;
}
if(dp[i] > maxn){
maxn = dp[i];
begin = pos;
end = i;
}
}cout << maxn << " "<<begin <<" " <<end<<" "<<endl;
} }
With the help of vector
1. #include<iostream>
2. #include<vector>
3. using namespace std;
4. const int N = 1e6 + 10;
5. int dp[N];
6. vector<int> arr;
7. int main(){
8. int t;
9. cin >> t;
10. while(t--){
11. int n;
12.
13. int begin, end, pos = 1;
14. cin >> n;
15. arr.push_back(0); //vector is automatically used from 0, and no legal person is changed
16. for(int i = 1; i <= n; i++){
17. int a;
18. cin >> a;
19. arr.push_back(a);
20. }
21. dp[1] = arr[1];
22. int maxn = -0x3f3f3f3f;
23. for(int i = 1; i <= n; i ++){
24. if(dp[i - 1] + arr[i] >= arr[i]){
25. dp[i] = dp[i - 1] + arr[i];
26. }
27. else{
28. dp[i] = arr[i];
29. pos = i;
30. }
31.
32. if(dp[i] > maxn){
33. maxn = dp[i];
34. begin = pos;
35. end = i;
36. }
37. }
38. cout << maxn << " " << begin << " " << end << " " << endl;
39. arr.clear(); //Note: all vector s must be deleted. If the next set of data is not affected, the array can be overwritten
40. }
41. }