01背包问题

代码1：（二维朴素做法）

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int dp[N][N]; // dp[0][0] = 0
int v[N],w[N];
int n,m;

int main(){
    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 = 0;j <= m;j++){
            dp[i][j] = dp[i-1][j];
            if (j - v[i] >= 0){
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
            }
        }

    cout << dp[n][m];
    return 0;
}

代码2：（一维滚动数组优化）

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int dp[N];
int n,m;
int v,w;
int main(){
    cin >> n >> m;
    for (int i = 1;i <= n;i++){
        cin >> v >> w; // 边输入边处理
        for (int j = m;j >= v;j--){
            dp[j] = max(dp[j],dp[j-v]+w);
        }
    }    
    cout << dp[m];
    return 0;
}

完全背包问题

代码1：三重循环（朴素）做法，数据加强后TLE

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

int n,m;
int dp[N][N];
int v[N],w[N];
int main(){
    cin >> n >> m;

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

    // i从1开始枚举，j从0开始枚举
    for (int i = 1;i <= n;i++)
        for (int j = 0;j <= m;j++)
            for (int k = 0;k*v[i]<=j;k++)
                dp[i][j] = max(dp[i][j],dp[i-1][j-k*v[i]] + k*w[i]);
    cout << dp[n][m] << endl;
    return 0;
}

代码2：（二维优化做法）

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

int n,m;
int dp[N][N];
int v[N],w[N];
int main(){
    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 = 0;j <= m;j++){
            dp[i][j] = dp[i-1][j];// 特判第一种情况
            if (j >= v[i]) dp[i][j] = max(dp[i][j],dp[i][j-v[i]]+w[i]);
        }

    cout << dp[n][m] << endl;
    return 0;
}

代码3：（第一维度优化做法）

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

int n,m;
int dp[2][N];
int v,w;
int main(){
    cin >> n >> m;

    for (int i = 1;i <= n;i++){
        cin >> v >> w;
        for (int j = 0;j <= m;j++){
            dp[i&1][j] = dp[(i-1)&1][j];
            if (j >= v) dp[i&1][j] = max(dp[i&1][j],dp[i&1][j-v] + w);
        }
    }    
    cout << dp[n&1][m] << endl;
    return 0;
}

代码4：（滚动数组优化做法）

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

int n,m;
int dp[N];
int v[N],w[N];
int main(){
    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++){
            dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
        }

    cout << dp[m] << endl;
    return 0;
}

多重背包问题

代码1：（三维朴素做法）

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

int dp[N][N];
int v[N],w[N],s[N];
int n,m;
int main(){
    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 = 0;j <= m;j++){
            // 比完全背包多一个物品件数限制
            for (int k = 0;k <= s[i] && j >= k*v[i];k++) dp[i][j] = max(dp[i][j],dp[i-1][j-k*v[i]] + k*w[i]);
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

代码2：（二进制优化做法）

#include <iostream>
#include <algorithm>
using namespace std;

// N的上限是n*logS == 1000*log2000
// M表示背包物品总体积不超过2010
const int N = 12000,M = 2010;

int n,m;
int v[N],w[N];
int dp[M];
int main(){
    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++;//组别先增加，下标从1开始
            v[cnt] = a*k;//整体体积
            w[cnt] = b*k;// 整体价值
            s -= k;
            k *= 2;// k = 1,2,4,8,...
        }
        // 处理最后的剩余一组
        if (s > 0){
            cnt ++;
            v[cnt] = a*s;
            w[cnt] = b*s;
        }
    }
    n = cnt;//枚举次数由个数变成重新划分的组别数
    // 求解优化后的01背包问题
    for (int i = 1;i <= n;i++)
        for (int j = m;j >= v[i];j--)
            dp[j] = max(dp[j],dp[j-v[i]] + w[i]);

    cout << dp[m] << endl;
    return 0;
}

分组背包问题

代码1：（二维朴素做法）

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;
int n,m;
int dp[N][N];
int v[N][N],w[N][N],s[N];

int main(){
    cin >> n >> m;
    for (int i = 1;i <= n;i++){
        cin >> s[i];
        for (int j = 0;j < s[i];j++){
            cin >> v[i][j] >> w[i][j];
        }
    }

    for (int i = 1;i <= n;i++)
        for (int j = 0;j <= m;j++){
            dp[i][j] = dp[i-1][j];// 不选
            for (int k = 0;k < s[i];k++){// 选第k件
                if (j >= v[i][k]) dp[i][j] = max(dp[i][j],dp[i-1][j-v[i][k]] + w[i][k]);
            }
        }
    cout << dp[n][m] << endl;
    return 0;
}

代码2：（一维滚动数组优化做法）

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;

int n,m;
int v[N][N],w[N][N],s[N];
int dp[N];

int main(){
    cin >> n >> m;
    for (int i = 1;i <= n;i++){
        cin >> s[i];
        for (int j = 0;j < s[i];j++){
            cin >> v[i][j] >> w[i][j];
        }
    }

    for (int i = 1;i <= n;i++)
        // 逆序枚举j
        for (int j = m;j >= 0;j--){
            for (int k = 0;k < s[i];k++){
               // if判断不能放在for的条件判断里面，相当于break
                if (j >= v[i][k]) dp[j] = max(dp[j],dp[j-v[i][k]] + w[i][k]);
            }
        }
    cout << dp[m] << endl;
    return 0;
}