背包问题

背包问题是使用dp的经典问题，本篇文章将讲解所有的背包问题，文章也会不断完善，不断通俗易懂。
背包问题是使用dp的经典问题，本篇文章将讲解所有的背包问题，文章也会不断完善，不断通俗易懂。
背包问题是使用dp的经典问题，本篇文章将讲解所有的背包问题，文章也会不断完善，不断通俗易懂。
背包问题是使用dp的经典问题，本篇文章将讲解所有的背包问题，文章也会不断完善，不断通俗易懂。

01背包

Acwing 2. 01背包问题
空间未优化版本

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int v[N], w[N], f[N][N];
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ){
        scanf("%d%d", &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];
            else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    printf("%d", f[n][m]);
    return 0;
}

空间优化版本

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int v[N], w[N], f[N];
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ){
        scanf("%d%d", &v[i], &w[i]);
    }
    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]);
        }
    }
    printf("%d", f[m]);
    return 0;
}

完全背包

Acwing 3. 完全背包问题
空间未优化版本

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int v[N], w[N], f[N][N];
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ){
        scanf("%d%d", &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];
            else f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
        }
    }
    printf("%d", f[n][m]);
    return 0;
}

空间优化版本

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int v[N], w[N], f[N];
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ){
        scanf("%d%d", &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]);
        }
    }
    printf("%d", f[m]);
    return 0;
}

多重背包(TODO)

Acwing 多重背包问题 I

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int v[N], w[N], s[N], f[N][N];
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) scanf("%d%d%d", &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] && j >= k * v[i]; k ++ ){
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
    }
    printf("%d", f[n][m]);
    return 0;
}

空间优化版本

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int v[N], w[N], s[N], f[N];
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) scanf("%d%d%d", &v[i], &w[i], &s[i]);
    for(int i = 1; i <= n; i ++ ){
        for(int j = m; j >= v[i]; j -- ){
            for(int k = 1; k <= s[i] && j >= k * v[i]; k ++ ){ // k 只取到1就可以了，因为f[j]代表了上一次循环的旧值和迭代1~s[i]的最大f[j]
                f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
            }
        }
    }
    printf("%d", f[m]);
    return 0;
}

二进制优化版本

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10; // log(2000) * 1000 = 11000
int v[N], w[N], f[N][N], num;
int main(){
    int n, m, vv, ww, s;
    scanf("%d%d", &n, &m);
    while(n -- ){
        scanf("%d%d%d", &vv, &ww, &s);
        for(int k = 1; k <= s; k <<= 1){
            v[ ++ num] = k * vv;
            w[num] = k * ww;
            s -= k;
        }
        if(s){
            v[ ++ num] = s * vv;
            w[num] = s * ww;
        }
    }
    for(int i = 1; i <= num; i ++ ){
        for(int j = 1; j <= m; j ++ ){
            if(j < v[i]) f[i][j] = f[i - 1][j];
            else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    printf("%d", f[num][m]);
    return 0;
}

内存溢出 Memory Limit Exceeded

二进制优化版本，内存优化

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 2000; // log(2000) * 1000 = 11000
int v[N], w[N], f[N], num;
int main(){
    int n, m, vv, ww, s;
    scanf("%d%d", &n, &m);
    while(n -- ){
        scanf("%d%d%d", &vv, &ww, &s);
        for(int k = 1; k <= s; k <<= 1){
            v[ ++ num] = k * vv;
            w[num] = k * ww;
            s -= k;
        }
        if(s){
            v[ ++ num] = s * vv;
            w[num] = s * ww;
        }
    }
    for(int i = 1; i <= num; i ++ ){
        for(int j = m; j >= v[i]; j -- ){
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    printf("%d", f[m]);
    return 0;
}