背包dp整理

01背包

    动态规划是一种高效的算法。在数学和计算机科学中,是一种将复杂问题的分成多个简单的小问题思想 ---- 分而治之。因此我们使用动态规划的时候,原问题必须是重叠的子问题。运用动态规划设计的算法比一般朴素算法高效很多,因为动态规划不会重复计算已经计算过的子问题。因为动态规划又可以称为“记忆化搜索”。

    01背包是介绍动态规划最经典的例子,同时也是最简单的一个。我们先看看01背包的是什么?

问题(01背包):
        有n个重量和价值分别为vi和ci的物品。从这些物品中挑出总重量不超过m的物品,求所有挑选方案中价值总和的最大值。

    这就是被称为01背包的问题。在没学习动态规划之前,我们看到这个问题第一反应会用dfs搜索一遍。那我们先使用这种方法来求解01背包问题:

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e3+1;
int n,m,v[N],c[N];
//从第i个物品开始挑选总重量不大于sumv的部分  
int dfs(int now,int sumv){
    int res;
    if(now==n+1) return res=0;//已经没有剩余物品
    if(sumv<v[now]) res=dfs(now+1,sumv);//无法挑选第i个物品
    else res=max(dfs(now+1,sumv),dfs(now+1,sumv-v[now])+c[now]);//比较挑和不挑的情况,选取最大的情况
    return res;
}
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&c[i]);
    printf("%d",dfs(1,m));
    return 0;
}
/*
期望得分:30分 
*/

    乍一看dfs好像就可以解决这个问题,那还有动态规划什么事。然而我们仔细分析一下时间复杂度,每一种状态都用选或者不选两种可能。所以我们可以得出使用dfs的时间复杂度为O(2^n)。显然这个方法不是一个很好的方法,因为这个时间复杂度太高了。我们仔细研究可以发现,造成时间复杂度这么高的原因是重复计算。既然我们找到复杂度这么高的原因,那我们就可以想办法减少它重复计算的次数。仔细分析容易想到,使用一个二维数组来记录每一次搜索的答案,这样我们就避免了重复计算。

    这样的小技巧,我们称之为记忆化搜索。我们只是小小的改变就让它的时间复杂度降低至O(nW)。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e3+1;
int n,m,v[N],c[N],dp[N][N*10];//保存每一次搜索的答案 
int dfs(int now,int sumv){
    if(dp[now][sumv]!=-1) return dp[now][sumv];
    int res;
    if(now==n+1) return dp[now][sumv]=0;
    if(sumv<v[now]) res=dfs(now+1,sumv);
    else res=max(dfs(now+1,sumv),dfs(now+1,sumv-v[now])+c[now]);
    return dp[now][sumv]=res;
}
int main(){
    memset(dp,-1,sizeof dp);//初始化dp数组的值,使其全为-1 
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&c[i]);
    printf("%d",dfs(1,m));
    return 0;
}
/*
期望得分:60-80分 
*/

  仔细分析,可以发现我们还可以有更简单的写法(转成递推):

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e3+1;
int n,m,v[N],c[N],dp[N][N*10];
//dp[i][j] 表示取了i个物品挑选出总重量不超过j的物品时,背包中的最大价值
int main(){
    memset(dp,-1,sizeof dp);
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&c[i]);
    for(int i=0;i<=m+1;i++) dp[n+1][i]=0;//还没开始挑选的时候,背包里的总价值为0
    for(int i=n;i;i--){
        for(int j=m;j>=0;j--){
            if(j<v[i]) dp[i][j]=dp[i+1][j];
            else dp[i][j]=max(dp[i+1][j],dp[i+1][j-v[i]]+c[i]);
        }
    }
    printf("%d",dp[1][m]);
    return 0;
}
/*
期望得分:60-80分 
*/

  然后dp[i][j]的仅由dp[i+1][j]||dp[i+1][j-v[i]]转移而来,于是我们可以滚动第一维:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e3+1;
int n,m,v[N],c[N],dp[2][N*10];
int main(){
    memset(dp,-1,sizeof dp);
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&c[i]);
    int now=0;//开启滚动 
    for(int i=0;i<=m;i++) dp[now][i]=0;//当前状态初始化 
    for(int i=n;i;i--){
        now^=1;
        for(int j=m;j>=0;j--){
            if(j<v[i]) dp[now][j]=dp[now^1][j];
            else dp[now][j]=max(dp[now^1][j],dp[now^1][j-v[i]]+c[i]);
        }
    }
    printf("%d",dp[now][m]);
    return 0;
}
/*
期望得分:100分 
*/

  凡是可以滚动的,必定可以降维。——shenben

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e3+1;
int n,m,v[N],c[N],dp[N*10];
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&c[i]);
    dp[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){//v[i]以后的j对答案没有贡献 
            dp[j]=max(dp[j],dp[j-v[i]]+c[i]);
        }
    }
    printf("%d",dp[m]);
    return 0;
}
/*
期望得分:100分 
*/

    使用递推方程直接求解的方法,我们称之为dp。因为他每一次的选取,都在动态的计算最优的情况。当然可能他局部不是最优,但是整体一定是最优解。这就是他和贪心算法最大的不同,贪心算法,每一次都是最优,但是整体不一定不是最优。

多重背包

 

问题(多重背包):
  就是一个0,1,2……k背包(往01背包上想就好了)
有n种重量和价值分别为vi和ci的物品,每种物品有si个。从这些物品中挑出总重量不超过m的物品,求所有挑选方案中价值总和的最大值

  搜索

//期望得分:30-70分 
#include<cstdio>
#include<algorithm>
#define N 10100
using namespace std;
int v[N],c[N],s[N],n,m;
int ans;
void dfs(int now,int sumv,int sumc){
    if(now==n+1){if(sumv<=m) ans=max(ans,sumc);return ;}
    dfs(now+1,sumv,sumc);
    for(int i=1;i<=s[now];i++) dfs(now+1,sumv+i*v[now],sumc+i*c[now]);
}
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++) scanf("%d%d%d",v+i,c+i,s+i);
    dfs(1,0,0);
    printf("%d",ans);
    return 0;
}

  记忆化搜索

//期望得分:60-100分 
#include<cstdio>
#include<algorithm>
#define N 10100
using namespace std;
int v[N],c[N],s[N],n,m;
int ans;
int dp[101][N];
int dfs(int now,int sumv){
    if(now==n+1) return 0;
    if(dp[now+1][sumv]) dp[now][sumv]=dp[now+1][sumv];
    else dp[now][sumv]=dfs(now+1,sumv);
    for(int i=1;i<=s[now];i++){
        if(sumv+i*v[now]>m) break;
        if(dp[now+1][sumv+i*v[now]]) dp[now][sumv]=max(dp[now][sumv],dp[now+1][sumv+i*v[now]]+i*c[now]);
        else dp[now][sumv]=max(dp[now][sumv],dfs(now+1,sumv+i*v[now])+i*c[now]);
    }
    return dp[now][sumv];
}
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++) scanf("%d%d%d",v+i,c+i,s+i);
    dfs(1,0);
    printf("%d",dp[1][0]);
    return 0;
}

  记忆化搜索转递推

//期望得分:60-100分 
#include<cstdio>
#include<algorithm>
#define N 10100
using namespace std;
int v[N],c[N],s[N],n,m;
int ans;
int dp[101][N];
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++) scanf("%d%d%d",v+i,c+i,s+i);
    for(int i=n;i;i--){
        for(int j=m;j>=0;j--){
            for(int k=0;k<=s[i];k++){
                if(j-k*v[i]<0) break;
                dp[i][j]=max(dp[i][j],dp[i+1][j-k*v[i]]+k*c[i]);
            }
        }
    }
    printf("%d",dp[1][m]);
    return 0;
}

  滚动数组(滚动第一维)

//期望得分:100分 
#include<cstdio>
#include<algorithm>
#define N 10100
using namespace std;
int v[N],c[N],s[N],n,m;
int ans;
int dp[2][N];
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++) scanf("%d%d%d",v+i,c+i,s+i);
    int now=0;
    for(int i=n;i;i--){
        now^=1;
        for(int j=m;j>=0;j--){
            for(int k=0;k<=s[i];k++){
                if(j-k*v[i]<0) break;
                dp[now][j]=max(dp[now][j],dp[now^1][j-k*v[i]]+k*c[i]);
            }
        }
    }
    printf("%d",dp[now][m]);
    return 0;
}

   降维(用二进制优化)

//期望得分:100分 
#include<cstdio>
#include<iostream>
using namespace std;
inline int read(){
    register int x=0,f=1;
    register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int N=1e5+10;
int n,m,cnt,xp[30];
int f[N*200],v[N],c[N];
int main(){
    for(int i=0;i<=25;i++) xp[i]=1<<i; 
    m=read();n=read();
    for(int i=1,x,y,z;i<=n;i++){
        x=read();y=read();z=read();
        for(int t=0;z>xp[t];t++){
            v[++cnt]=x*xp[t];
            c[cnt]=y*xp[t];
            z-=xp[t];
        }
        if(z>0){
            v[++cnt]=x*z;
            c[cnt]=y*z;
        }
    }
    for(int i=1;i<=cnt;i++){
        for(int j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+c[i]);
        }
    }
    printf("%d",f[m]);
    return 0;
}

其他背包dp自行整理

原文地址:https://www.cnblogs.com/shenben/p/6041642.html