Basic idea of dynamic programming
Understand the basic idea of dynamic programming
- Determine state variables (functions)
- Determine the state transition equation (recursive relationship)
- Determine boundary
Various knapsack problem contents, ideas, examples and code implementation
Basic 0-1 knapsack problem
The basic idea of 0-1 knapsack problem
0-1 knapsack detailed problem solution
0-1 knapsack simplification / dimensionality reduction idea – it's a little complicated, but it's very detailed, mainly: 1 Reverse order: because the information obtained in this layer is recursively obtained by the previous layer, the reverse order protects the information of the previous layer to ensure the correctness of the information obtained in this layer; 2. The essence of dimensionality reduction is that the information can be covered in the recursive process without affecting the results, because the information of layer i is only related to layer i-1 and has nothing to do with layer i-2.
Title: The most basic 0-1 knapsack problem
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int wei[N],val[N];
//int f[N][N];//f[i][j] represents the maximum value of I items in the backpack with capacity j
int f[N];
int n,wemax;
int main()
{
cin>>n>>wemax;//4 5
for(int i=1;i<=n;i++)
{
cin>>wei[i]>>val[i];
}
/*Not simplified:
for(int i=1;i<=n;i++)
{
for(int j=0;j<=wemax;j++)//j It is the [0,wemax] of capacity to capacity. In each case, consider whether to put it or not, and keep the larger value
{
f[i][j]=f[i-1][j];//Don't put the value of the ith item
if(j>=wei[i]) f[i][j]=max(f[i][j],f[i-1][j-wei[i]]+val[i]);
/* Explanation:
j>=wei[i] The backpack itself has enough capacity to put the i-th item
Do you prefer not to put the i-th item? Is it more valuable or more valuable (if you put it, some of the previous items may have to be taken out)
f[i][j]，That is, f[i-1][j] is the value when it is not released
f[i-1][j-wei[i]]+val[i]Is the maximum value when the capacity is j-wei[i] + the value of the current item
That is, at this time, the value is the largest from the previous situation and the ith item can be put down
The problem with abstraction is why f[i-1] is OK
Because according to the definition, f[i-1] is the optimal solution in its case, the optimal solution + v must be the optimal solution in f[i]
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=wemax;j++)
{
cout<<f[i][j]<<" ";
}
cout<<endl;
}
cout<<f[n][wemax]<<endl;
*/
//simplify:
for(int i=1;i<=n;i++)
{
//Reverse order
//Because the determination of f[j] of layer i must use the f[j] of layer i-1, and the obtained f[j] of this layer cannot be used, the reverse order must be used.
//One dimensional storage is to cover the previous information and reduce the space
for(int j=wemax;j>=wei[i];j--)
{
f[j]=max(f[j],f[j-wei[i]]+val[i]);
//cout<<f[j]<<" ";
}
//cout<<endl;
}
/*for(int i=1;i<=n;i++)
{
cout<<f[i]<<" ";
}*/
cout<<f[wemax]<<endl;
return 0;
}
/*
Not simplified:
f[i][j]:
j:1 2 3 4 5
0 2 2 2 2 2
0 2 4 6 6 6
0 2 4 6 6 8
0 2 4 6 6 8
simplify:
f[i]: 2 4 6 6 8
Change in cycle:
5 4 3 2 1 <-order
2 2 2 2 2
6 6 6 4
8 6 6
8 6
*/
0-1 knapsack problem with two constraints
Title: NASA's Food Program
#include<bits/stdc++.h>
using namespace std;
const int N=1e3;
int wei[N],v[N],ca[N];
int f[N][N];
struct node{
int v;
int w;
int ca;
}food[N];
int main()
{
int maxv,maxw;
cin>>maxv>>maxw;
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>food[i].v>>food[i].w>>food[i].ca;
}
for(int i=1;i<=n;i++)
{
for(int j=maxv;j>=food[i].v;j--)//First limit
{
for(int k=maxw;k>=food[i].w;k--)//Second limit
{
f[j][k]=max(f[j][k],f[j-food[i].v][k-food[i].w]+food[i].ca);
}
}
}
cout<<f[maxv][maxw];
return 0;
}
Complete knapsack problem in which items can be selected infinitely
Title: Complete knapsack problem , that is, one more layer of circulation on the basis of 0-1 backpack, Detailed text explanation
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int f[N];
int wei[N],val[N];
/*
Combine K selected items with wei[i], f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i])
Optimization:
f[i , j ] = max( f[i-1,j] , f[i-1,j-wei]+val , f[i-1,j-2*wei]+2*val , f[i-1,j-3*wei]+3*val , .....)
f[i , j-v]= max( f[i-1,j-wei] , f[i-1,j-2*wei] + val , f[i-1,j-3*wei]+2*val , .....)
-------->Then f [i] [J] = max (f [I-1] [J], f [I, j-wei] + VAL);
Compare 0-1 knapsack f [i] [J] = max (f [I-1] [J], f [I-1, j-wei] + VAL);
Before further optimization, f[i][j]=f[i-1][j];
After further optimization: if the 0-1 knapsack is f[i-1,j-wei]+val, it needs to be in reverse order, because it is related to the i-1 layer, and the range is [m, wei[i]]
However, the complete knapsack is f[i,j-wei]+val), which does not need to be in reverse order. It can be from small to large, and the range is [wei[i], m]
-------->State transition equation: f[j] = max(f[j],f[j-wei[i]]+val[i])
*/
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>wei[i]>>val[i];
}
for(int i=1;i<=n;i++)
{
for(int j=wei[i];j<=m;j++)//Enumerate from small to large because layer i is independent of layer i-1
{
f[j]=max(f[j],f[j-wei[i]]+val[i]);
}
}
cout<<f[m];
}
Multiple knapsack problem in which objects can be selected finite times 1
Title: Multiple knapsack problem 1
Based on the complete knapsack problem, a limit of K < = num [i] & & K * Wei [i] < = J is added to limit the number of items selected.
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int f[N][N];
int wei[N],val[N],num[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>wei[i]>>val[i]>>num[i];
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
for(int k=0;k<=num[i]&&k*wei[i]<=j;k++)
f[i][j]=max(f[i][j],f[i-1][j-wei[i]*k]+val[i]*k);
}
}
cout<<f[n][m];
return 0;
}
Multiple knapsack problem 2, binary optimization method
Title: Multiple knapsack problem 2 ,Topic Video Explanation
I didn't particularly understand. I'll listen to the video carefully when I'm free
#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int f[N];
struct Good{
int wei,val;
};
int main()
{
int n,m;
cin>>n>>m;
vector<Good> goods;
for(int i=1;i<=n;i++)
{
int w,v,s;
cin>>w>>v>>s;
for(int k=1;k<=s;k*=2)
{
s-=k;
goods.push_back({w*k,v*k});
}
if(s>0) goods.push_back({w*s,v*s});
}
for(auto good:goods)
{
for(int j=m;j>=good.wei;j--)
{
f[j]=max(f[j],f[j-good.wei]+good.val);
}
}
cout<<f[m];
return 0;
}
Grouping knapsack problem
Title: Grouping knapsack problem
Solution: Detailed text explanation,Video problem solving
It is said to be the general case of multiple knapsack problem
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int f[N];
int wei[N][N],val[N][N],s[N];//s represents the number of items in group i
/*
0-1: Maximum value of the first i items with volume less than j
Group backpack: the maximum value of the first group i items whose volume is less than j
*/
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s[i];
for(int j=0;j<s[i];j++)
{
cin>>wei[i][j]>>val[i][j];
}
}
for(int i=1;i<=n;i++)//stage
{
for(int j=m;j>=0;j--)//i. j. common composition state
{
for(int k=0;k<s[i];k++)//k is decision
{
if(wei[i][k]<=j)
{
f[j]=max(f[j],f[j-wei[i][k]]+val[i][k]);
}
}
}
}
cout<<f[m]<<endl;
return 0;
}
0-1 knapsack extension question
Title: Flowers
Resolution: Detailed explanation of Luogu
Idea:
I don't particularly understand this question. I'll consider it later
UN optimized code:
#include<bits/stdc++.h>
using namespace std;
const int maxn=105, mod = 1000007;
int n, m, a[maxn], f[maxn][maxn];
int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>a[i];
f[0][0] = 1;
for(int i=1; i<=n; i++)
for(int j=0; j<=m; j++)
for(int k=0; k<=min(j, a[i]); k++)
f[i][j] = (f[i][j] + f[i-1][j-k])%mod;
cout<<f[n][m]<<endl;
return 0;
}
The optimized version code is as follows:
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int f[N];
int a[N];
int mod=1000007;
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
f[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=0;j--)
{
for(int k=1;k<=min(a[i],j);k++)
{
f[j]=(f[j]+f[j-k])%mod;
}
}
}
cout<<f[m]<<endl;
}
More knapsack problem summary and explanation articles supplement:
Article 1, in addition to the content contained in this article, there is also the mixed knapsack problem, that is, each item can be selected a different number of times, which is a bit like "flower arrangement", that is, limit the number of times each item is selected, but the number of times each item is different
In Article 2, each model and state transition formula are analyzed in detail
summary
In the case of introduction to dynamic planning, I wrote several topics related to backpack, but I still know a little. I don't have the ability to independently analyze and solve new dynamic planning problems. I can only recall the problems and use methods that have been done according to my memory, and then consider how to solve new problems. I hope more and more questions can make the situation not so cramped