DP(动态规划)中常见背包问题的总结

66 阅读 0 评论 44 点赞

我是靠谱客的博主魁梧刺猬，最近开发中收集的这篇文章主要介绍DP(动态规划)中常见背包问题的总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

关于背包问题比较经典的讲解应该是 dd大牛的背包九讲
学习视频的话推荐大雪菜老师的讲解，大雪雪菜老师讲的详细并且易懂，我就不像在博客中分析思路了。
前6种
后3种
视频中的题目刷题地址
各类背包问题，大体都是讲，在背包容积一定的情况下，怎样选择物品使价值之和最大。
1. 01背包(每个物品至多选一次)
时间复杂n*C

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
int f[N];
int main(){
int n,v,w,C;
cin>>n>>C;
for(int i=1;i<=n;i++){
cin>>v>>w;
for(int j=C;j>=v;j--)f[j]=max(f[j],f[j-v]+w);
}
cout<<f[C]<<endl;
}

2. 完全背包(每个物品可以选任意次)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
int f[N];
int main(){
int n,v,w,C;
cin>>n>>C;
for(int i=1;i<=n;i++){
cin>>v>>w;
for(int j=v;j<=C;j++)f[j]=max(f[j],f[j-v]+w);
}
cout<<f[C]<<endl;
}

3. 多重背包(每个物品可以选ai次,ai是题目给出的常数)
这里只提供了二进制的优化方法，时间复杂度是 $n * v * l o g (s)$ ,如果题目卡log算法的时间的话，那么就得用优先队列的优化方法,视频里有提到过。

#include<bits/stdc++.h>
#include<vector>
using namespace std;
const int N=2e3+10;
struct good{
int v,w;
};
vector<good>goods;
int f[N];
int main(){
int n,C,v,w,s;
cin>>n>>C;
for(int i=1;i<=n;i++){
cin>>v>>w>>s;
for(int k=1;k<=s;k*=2){
s-=k;
goods.push_back({v*k,w*k});
}
if(s>0) goods.push_back({v*s,w*s});
}
for(auto i:goods)
for(int j=C;j>=i.v;j--)
f[j]=max(f[j],f[j-i.v]+i.w);
cout<<f[C]<<endl;
}

4. 混合背包(每个物品都有不同的次数限制)

#include<bits/stdc++.h>
#include<vector>
using namespace std;
const int N=2e3+10;
struct good{
int v,w;
bool f;
};
vector<good>goods;
int f[N];
int main(){
int n,C,v,w,s;
cin>>n>>C;
for(int i=1;i<=n;i++){
cin>>v>>w>>s;
if(s==-1)goods.push_back({v,w,1});
else if(s==0)goods.push_back({v,w,0});
else {
for(int k=1;k<=s;k*=2){
s-=k;
goods.push_back({v*k,w*k,1});
}
if(s>0) goods.push_back({v*s,w*s,1});
}
}
for(auto i:goods){
if(!i.f)
for(int j=i.v;j<=C;j++)
f[j]=max(f[j],f[j-i.v]+i.w);
else
for(int j=C;j>=i.v;j--)
f[j]=max(f[j],f[j-i.v]+i.w);
}
cout<<f[C]<<endl;
}

5. 二维01背包(增加了一维限制)

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N][N];
int main(){
int n,v,w,m,C,M;
cin>>n>>C>>M;
for(int i=1;i<=n;i++){
cin>>v>>m>>w;
for(int j=C;j>=v;j--)
for(int k=M;k>=m;k--)
f[j][k]=max(f[j][k],f[j-v][k-m]+w);
}
cout<<f[C][M]<<endl;
}

6.分组背包(有n个不同种类的物品,每个组s个物品,每组至多选一个物品)

因为每组只能选一个所以对于每个组，枚举每一份空间v，在每一组s+1种决策下的最大值，然后再继续下一组。

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N],v[N],w[N];
int main(){
int n,s,C;
cin>>n>>C;
for(int i=1;i<=n;i++){
cin>>s;
for(int j=1;j<=s;j++)cin>>v[j]>>w[j];
for(int j=C;j>=0;j--){
for(int k=1;k<=s;k++)
if(j>=v[k])f[j]=max(f[j],f[j-v[k]]+w[k]);//不能只写大于
}
}
cout<<f[C]<<endl;
}

7. 背包问题求方案数(多少种方法使价值最大)
注意可能有几种相同的体积使价值最大。

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int N=1010,mod=1e9+7;
int f[N],g[N];
int main() {
int n,C,v,w,ma=0,ans=0;
g[0]=1;
cin>>n>>C;
for(int i=1;i<=n;i++){
cin>>v>>w;
for(int j=C;j>=v;j--){
int t,s=0;
t=max(f[j],f[j-v]+w);
if(t==f[j])s+=g[j];
if(t==f[j-v]+w)s+=g[j-v];
if(s>=mod)s-=mod;
g[j]=s,f[j]=t;
}
}
for(int i=1;i<=C;i++) ma=max(f[i],ma);
for(int i=1;i<=C;i++)
if(f[i]==ma){
ans+=g[i];
if(ans>=mod)ans-=mod;
}
cout<<ans<<endl;
}

分组背包

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define min(a,b) (a<b?a:b)
using namespace std;
int a[801];
int p[801][801];
long long f[801][801];
int n,m,i,j,k,l,K,Y;
int main()
{
//
freopen("a.in","r",stdin);
scanf("%d%d%d%d",&n,&m,&K,&Y);
fo(i,1,n)
scanf("%d",&a[i]);
fo(i,1,n)
{
fo(j,1,m)
{
scanf("%d",&p[i][j]);
if (j<Y)
p[i][j]+=a[i]*j;
}
}
memset(f,127,sizeof(f));
f[0][0]=0;
fo(i,0,n-1)
{
fo(j,0,K)
if (f[i][j]<800000000000ll)
{
fd(k,min(K-j,m),0)
f[i+1][j+k]=min(f[i+1][j+k],f[i][j]+p[i+1][k]);
}
}
printf("%lldn",f[n][K]);
}