算法 — 背包问题详解

经典算法之背包求最大最小值问题
经典算法之背包计数问题

输入

4 5
1 2
2 4
3 4
4 5

输出

8

核心思路

1. 矩阵 f 初始化为全零，这样可以保证只要体积不超过 j 都能装入
f[i][j] : 即从前 i 个物品中选，总体积不超过 j 的方案数。
f[i - 1][j - v] 表示： 当前为要处理的物品 i， 当满足 j >= v 时， 当前物品可以装入，
计算装入后是否会使得总价值变大，所以需要从之前的 i - 1, j - v, 转移过来用来代表 f[i][j]

当背包容量够时：
选：f[i][j] = f[i - 1][j - v[i]] + w[i]。
不选：f[i][j] = f[i - 1][j] 。
最终取对两者取max

可以打印出来看下结果：
装入前一个物品的结果（1 2）：0 2 2 2 2 2 
装入前一个物品的结果（2 4）：0 2 4 6 6 6 
装入前一个物品的结果（3 4）：0 2 4 6 6 8 
装入前一个物品的结果（4 5）：0 2 4 6 6 8 

#include 
using namespace std;

const int N = 1010;

int n, m;
int f[N][N];

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

代码简述：
利用滚动数组，即所以物品放于一维的空间上操作，当需要由上一状态转移过来了，为了不破坏前一阶段的数据，所以需要注意，j 从 m ~ v, 而 小于 v 的部分即为不选，不需要做任何操作，直接从上一状态转移过来即可

#include 
using namespace std;

const int N = 1010;

int n, m;
int f[N];

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

输入

4 5
1 2
2 4
3 4
4 5

输出

10

类比 01 背包问题，完全背包满足在体积不超过 j 的情况下 可以装无限个，所以可以通过去判断所有可能的情况，来判断价值的最大值

#include 
using namespace std;

const int N = 1010;

int n, m;
int f[N][N];

int main() {
    
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) { //依次加入每个背包
        int v, w;
        cin >> v >> w;
        for (int j = 0; j <= m; j ++ ) { // 依次计算 子状态
            for (int k = 0; k * v <= j; k ++ ) //循环判断再满足体积不超过 j 的情况下价值最大
                f[i][j] = max(f[i][j], f[i-1][j - k * v] + k * w); //这里不需要特判不装的时候， 因为当k = 0 时，即为不装的情况。
        }
    }
    
    
    cout << f[n][m];
    
    
    return 0;
}

思路（非常经典）

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w ,  f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max(            f[i-1,j-v]   ,  f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
由上两式，可得出如下递推关系： 
                        f[i][j]=max(f[i,j-v] + w , f[i-1][j])  //即选与不选两种状态

注意完全背包问题再转换为一维时， j 从 v ~ m ，由推导式可以看出，f[i][j] 是基于当前的状态，而不是上一状态转移过来，就得使劲污染

#include 
using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main() {
    
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) { //依次加入每个背包
        int v, w;
        cin >> v >> w;
        for (int j = v; j <= m; j ++ ) { 
            f[j] = max(f[j], f[j - v] + w);
        }
    }
    
    
    cout << f[m];
    
    
    return 0;
}

输入

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出

10

完全背包问题的特殊形式，每个物品不能超过 s 件

#include 
using namespace std;

const int N = 110;

int n, m;
int f[N][N];

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

这里奉上大佬的优化讲解 ： 二进制优化多重背包的思路

#include 
using namespace std;

const int N = 2010;
typedef pair PII;

int n, m;
int f[N];

vector G;




int main() {
    
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++ ) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int k = 1; k <= s; k *= 2) {
            s -= k;
            G.push_back({k * v, k * w});
        }
        if (s > 0) G.push_back({s * v, s * w}); //把最后剩余的部分装入进去;
    }
    
    
    //利用上述就可以跑 01 背包模型啦
    
    for (int i = 0; i < G.size(); i ++ ) {
        int v = G[i].first, w = G[i].second;
        for (int j = m; j >= v; j -- ) {
            f[j] = max(f[j], f[j - v] + w);
        }
    }
    
    cout << f[m];
    
    
    return 0;
}

输入

3 5
2
1 2
2 4
1
3 4
1
4 5

输出

8

同 01 背包问题，只需遍历每一组的每一个物品，每次都将每种状态保存起来，最终选择出最大的价值

#include 
using namespace std;

const int N = 110;

int n, m;

int f[N][N], s[N], v[N][N], w[N][N];

int main() {
    
    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 = 0; j <= m; j ++ ) { 
            for (int k = 0; k <= s[i]; k ++ ) { //遍历组内的每一个物品
                
                if (j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
            }
        }
    }
    
    cout << f[n][m];
    
    return 0;
}

#include 
using namespace std;

const int N = 110;

int n, m;

int f[N], s[N], v[N][N], w[N][N];

int main() {
    
    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 >= 0; j -- ) {
            for (int k = 0; k <= s[i]; k ++ ) {
                
                if (j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
            }
        }
    }
    
    cout << f[m];
    
    return 0;
}