一、背包问题

背包问题分类

1.1、0-1背包问题

1.1.1朴素版做法

void beibao1(){
    const int N = 1e3 + 5;
    int n,m;
    int v[N],w[N];
    int f[N][N] = {{0}};
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> v[i] >> w[i];
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++){
            if(j < v[i]) f[i][j] = f[i-1][j];
            if(j >= v[i]) f[i][j] = max(f[i- 1][j],f[i-1][j - v[i]] + w[i]);
        }
//    for(int i = 1;i <= n;i++){ //打印矩阵
//        for(int j = 1;j <= m;j++) {
//            cout << f[i][j] << " ";
//        }
//        cout << endl;
//    }
 
 
    cout << f[n][m] << endl;
}

1.1.2 一维优化版

void beibao2(){
    const int N = 1e3 +5 ;
    int f[N] = {0};
    int v[N],w[N];
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> v[i] >> w[i];
    for(int i = 1;i <= n;i++){
        for(int j = m;j >= v[i];j--) //这里原来有个思维误区,不是很能理解J从大到小循环,J从大到小循环和从小刀到大循环结果其实是一样的,它本来依赖的是上一层的值,和左右无关;如果这里从小到大循环,那么相当于上一层的值被覆盖了。
            f[j] = max(f[j],f[j - v[i]] + w[i]);
    }
//    for(int i = 1;i <= m;i++)
//        cout << f[i] << " ";
    cout << f[m] << endl;
}
 

1.2、完全背包问题

1.2.1 朴素做法,容易超时
概念

/完全背包问题,要点:曲线救国
//version 1:朴素版本
void completebeibao(){
    const int N = 1e3 +5 ;
    int n,m;
    int v[N],w[N];
    int f[N][N] = {{0}};
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> v[i] >> w[i];
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            for(int k = 0;k * v[i] <= j;k++)
                f[i][j] = max(f[i][j],f[i-1][j - v[i] * k] + w[i] * k);
 
    cout << f[n][m] << endl;
}
//4 5
//1 2
//2 4
//3 4
//4 5
 

1.2.2 优化做法
推导过程

//version 2:优化版本
void completebeibaoOptimize(){
    const int N = 1e3 +5 ;
    int n,m;
    int v[N],w[N];
    int f[N][N] = {{0}};
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> v[i] >> w[i];
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++){
            if(j < v[i]) f[i][j] = f[i - 1][j];
            if(j >= v[i]) f[i][j] = max(f[i - 1][j],f[i][j - v[i]] + w[i]);
        }
    cout << f[n][m] << endl;
}

1.2.3 一维优化版本

//version 3:一维优化
void completebeibaoOneDimen(){
    const int N = 1e3 +5 ;
    int n,m;
    int v[N],w[N];
    int f[N] = {0};
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> v[i] >> w[i];
    for(int i = 1;i <= n;i++)
        for(int j = v[i];j <= m;j++){
            f[j] = max(f[j],f[j - v[i]] + w[i]); //这里需要的是第i层 j - v[i],所以仍然是正向for循环
        }
 
 
    cout << f[m] << endl;
}

1.3、多重背包问题

1.3.1 朴素版本

void duochongbeibao(){
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> v[i] >> w[i] >> s[i];
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            for(int k = 0; k <= s[i] && k * v[i] <= j;k++)
                f[i][j] = max(f[i][j],f[i - 1][j - v[i] * k] + k * w[i]);
                
    cout << f[n][m] << endl;
}

1.3.2 二进制优化版本
多重背包问题不能类似于完全背包那样直接利用公式优化,但是可以利用二进制优化,把所有物品重新分租成0-1背包,然后再利用0-1背包的算法去求取最大价值

const int N = 21000;
int f[N];
int v[N];
int w[N];
void duochongbeibaoOptimize(){
    int n,m;
    cin >> n >> m;
    int cnt = 0;
    for(int i = 1;i <= n;i++){
        int a,b,s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s){
            cnt++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if(s > 0){
            cnt++;
            v[cnt] = a*s;
            w[cnt] = b*s;
        }
    }
    
    n = cnt;
    for(int i = 1;i <= n;i++)
        for(int j = m; j>= v[i];j--)
            f[j] = max(f[j],f[j - v[i]] + w[i]);
        
    cout << f[m];    
}

1.4、分组背包问题

1.4.1 一维版本

void Groupbeibao(){
    const int N = 110;
    int n,m;
    int v[N][N],w[N][N],s[N];
    int f[N];
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        cin >> s[i];
        for(int j = 1;j <= s[i];j++){
            cin >> v[i][j] >> w[i][j];
        }
    }
    
    for(int i = 1;i <= n;i++)
        for(int j = m; j >= 1;j--)
            for(int k = 1; k <= s[i];k++)
                if(v[i][k] <= j)
                    f[j] = max(f[j],f[j - v[i][k]] + w[i][k]);
                
    cout << f[m] << endl;            
                
                
}

二、线性DP

2.1 数字三角形
线性DP图解

void NumTriangle(){
    const int N = 510,INF = 1e9;
    int n;
    int a[N][N];
    int f[N][N];
    cin >> n;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= i;j++)
            cin >> a[i][j];

    for(int i = 0;i <= n;i++)
        for(int j = 0;j <= i + 1;j++)
            f[i][j] = -INF;

    f[1][5] = a[1][6];
    for(int i = 2;i <= n;i++)
        for(int j = 1;j <= i;j++)
            f[i][j] = max(f[i - 1][j - 1] + a[i][j],f[i - 1][j] + a[i][j]);

    int res = -INF;
    for(int i = 1;i <= n;i++) res = max(res,f[n][i]);
    cout << res;
};

2.2 最大上升子序列
最长上升子序列题解

void maxascendsubsqequence(){
    const int N = 1010;
    int n;
    int a[N],f[N];
    cin >> n;
    for(int i = 1;i <= n;i++ ) cin >> a[i];

    for(int i = 1;i <= n;i++){
        f[i] = 1;
        for(int j = 1;j < i;j++)
            if(a[j] < a[i])
                f[i] = max(f[i],f[j] + 1);
    }

    int res = 0;
    for(int i = 1;i <= n;i++) res = max(res,f[i]);
    cout << res;
}

2.3最大上升子序列2(数据增大版本,需要NlogN复杂度)

void maxaxcendsubsequence2(){
    const int N = 100010;
    int n;
    int a[N];
    int q[N];
    cin >> n;
    for(int i = 0;i < n;i++) cin >> a[i];
    int len = 0;
    q[0] = -2e9;
    for(int i = 0;i < n;i++){
        int l = 0,r = len;
        while(l < r){
            int mid = l + r +1 >> 1;
            if(q[mid] < a[i]) l = mid;
            else r = mid -1 ;
        }
        len = max(len,r + 1);
        q[r + 1 ] = a[i];
    }

    cout << len << endl;
}

2.3最长公共子序列
最长公共子序列

void maxcommonsubseq(){
    
    char a[N],b[N];
    int n,m;
    cin >> n >> m;
    scanf("%s%s",a + 1,b+ 1);
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++){
            f[i][j] = max(f[i - 1][j],f[i][j - 1]);
            if(a[i] == b[j]) f[i][j] = max(f[i][j],f[i - 1][j - 1] + 1);
        }

    cout << f[n][m] << endl;
}

2.3最短编辑距离
最短编辑距离

const int N = 1010;
int f[N][N];
char a[N],b[N];
void ShortestEditDistance(){
    int n,m;
    scanf("%d%s",&n,a + 1);
    scanf("%d%s",&m,b+ 1);
    for(int i = 0;i <= n;i++) f[i][0] = i;
    for(int j = 0;j <= m;j++) f[0][j] = j;
    
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++){
            f[i][j] = min(f[i][j - 1] + 1,f[i - 1][j] + 1);
            if(a[i] == b[j]) f[i][j] = min(f[i][j],f[i - 1][j - 1]);
            else f[i][j] = min(f[i][j],f[i - 1][j - 1] + 1);
        }  
    cout << f[n][m] << endl;
}
最后修改:2021 年 09 月 22 日 05 : 23 PM
如果觉得我的文章对你有用,请随意赞赏