动态规划专题一：线性dp

第一篇博客随笔，被迫写的bushi

上课讲的动态规划入门，还是得总结一下吧

背包

01背包

背包有容量限制，每一件物品只能够取一件（这就是为什么j从V至v[i]循环的原因）

思路：f数组表示当前状态的最佳情况，每一种物品就对应两种状态 1.选 2.不选，这样状态转移方程就出来了

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 int N,V;

 4 int v[10009],w[10009],f[50009];//v是物品的体积，w是物体的价值

 5 int main(){

 6     cin>>V>>N;

 7     for(int i=1;i<=N;i++){

 8         cin>>v[i]>>w[i];

 9         w[i]*=v[i];

10     }

11     for(int i=1;i<=N;i++)

12         for(int j=V;j>=v[i];j--)

13             f[j]=max(f[j],f[j-v[i]]+w[i]);

14     cout<<f[V];

15     return 0;

16 }

完全背包

背包有容量限制，每一件物品能够取无数件（这就是为什么j从v[i]至V循环的原因）注意与01背包进行区分

思路：f数组表示当前状态的最佳情况（一样的），每一种物品就不止对应两种状态了，这就是与01背包的本质区别。所以状态转移方程不变，就只需要改变循环遍历的顺序啦

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 int N,V;

 4 int v[1005],w[1005],f[1005];//v是物品的体积，w是物品的价值

 5 int main(){

 6     cin>>N>>V;

 7     for(int i=1;i<=N;i++) cin>>v[i]>>w[i];

 8     for(int i=1;i<=N;i++)

 9         for(int j=v[i];j<=V;j++)

10             f[j]=max(f[j],f[j-v[i]]+w[i]);

11     cout<<f[V];

12     return 0;

13 }

多重背包

背包有容量限制，每一件物品能够取规定数件(所以要拆分成01背包啊这就是思路)三种做法：1直接拆分2二进制拆分3单调队列（因为太菜，单调队列代码以后贴）a bushi

1直接拆分

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 int n,m;

 4 int f[10000002],v[1000005],w[1000005],c[1000005];

 5 int main(){

 6     cin>>n>>m;

 7     for(int i=1;i<=n;i++)

 8         cin>>v[i]>>w[i]>>c[i];

 9     f[0]=0;//v是价值，w是体积

10     for(int i=1;i<=n;i++){

11         for(int j=1;j<=c[i];j++){

12             for(int k=m;k>=w[i];k--)

13                 f[k]=max(f[k],f[k-w[i]]+v[i]);

14         }

15     }

16     cout<<f[m];

17     return 0;

18 }

2二进制拆分（注意输入时的预处理拆分）

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 int n,m,fl=1;

 4 int f[10000002],v[1000005],w[1000005],c[1000005];

 5 int main(){

 6     cin>>n>>m;

 7     for(int i=1;i<=n;i++){

 8         int x,y,z;

 9         cin>>x>>y>>z;

10         for(int j=1;j<=z;j=j<<1){

11             v[++fl]=j*x;w[fl]=j*y;

12             z-=j;

13         }

14         if(z>0) v[++fl]=x*z,w[fl]=y*z;

15     }

16     for(int i=1;i<=fl;i++){

17         for(int j=m;j>=w[i];j--){

18             f[j]=max(f[j],f[j-w[i]]+v[i]);

19         }

20     }

21     cout<<f[m];

22     return 0;

23 }

3单调队列(坑待填)

分组背包

背包有容量限制，每一组最多取一件物品

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 int w[50],c[50],v,n,t,a[11][31],f[220];

 4 int main(){

 5     cin>>v>>n>>t;

 6     for(int i=1;i<=n;i++){

 7         int x;

 8         cin>>w[i]>>c[i]>>x;

 9         a[x][0]++;

10         a[x][a[x][0]]=i;

11     }

12     for(int k=1;k<=t;k++){

13         for(int j=v;j>=0;j--){

14             for(int p=1;p<=a[k][0];p++){

15                 if(j>=w[a[k][p]])    f[j]=max(f[j-w[a[k][p]]]+c[a[k][p]],f[j]);

16             }

17         }

18     }

19     cout<<f[v];

20     return 0;

21 }

混合背包

就是把以上四种背包问题揉成了一道题，就分类讨论啊

就不贴代码了，贴一道题吧

基本上就这些了吧，遇到问题再更新吧

巴特西

动态规划专题一：线性dp

最新文章

热门文章