背包问题

背包问题指的是给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。它是一个经典的动态规划问题，有很多种变体（如01背包，完全背包，多重背包等）。

一、01背包问题

01背包问题指的是给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价值最高。每种物品只能 选择一次。

例题1.1 2.01背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 $v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。接下来有 N 行，每行两个整数 $v_i$,$w_i$，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围
$0<N, V≤1000$

$0<v_i, w_i≤1000$

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

8

解题思路

1. 定义状态：$f[i][j]$表示前i个物品放入容量为j的背包中所能获得的最大价值。
2. 状态转移方程：$f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])$，即第i个物品放入背包和不放入背包的最大值。
3. 初始化：$f[0][j] = 0$，$f[i][0] = 0$，表示背包容量为0或物品数量为0时，最大价值为0。
4. 遍历顺序：外层循环遍历物品，内层循环遍历背包容量，从小到大遍历。

代码实现

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> v(N+1, 0);
    vector<int> w(N+1, 0);
    for(int i=1; i<=N; i++) {
        cin >> v[i] >> w[i];
    }
    // 创建dp数组
    vector<vector<int>> dp(N+1, vector<int>(V+1, 0));  // 注意是N+1，V+1，因为要避免越界和保证出现体积为V的状态
    // 状态转移
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=V; j++) {
            if(j >= v[i]) {
                // 如果当前背包容量大于等于物品体积，则可以选择放入或不放入
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+w[i]);
            } else {
                // 如果当前背包容量小于物品体积，则只能选择不放入
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[N][V];
    return 0;
}

二、完全背包问题

完全背包问题指的是给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价值最高。每种物品可以 选择多次。

例题2.1 3.完全背包问题

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。第 i 种物品的体积是 $v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。接下来有 N 行，每行两个整数 $v_i$,$w_i$，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围
$0<N, V≤1000$

$0<v_i, w_i≤1000$

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例

10

解题思路

1. 定义状态：$f[i][j]$表示前i种物品放入容量为j的背包中所能获得的最大价值。
2. 状态转移方程：$f[i][j] = max(f[i-1][j], f[i][j-v[i]] + w[i])$，即第i种物品放入背包和不放入背包的最大值。
3. 初始化：$f[0][j] = 0$，$f[i][0] = 0$，表示背包容量为0或物品数量为0时，最大价值为0。
4. 遍历顺序：外层循环遍历物品，内层循环遍历背包容量，从小到大遍历。

代码实现

#include<iostream>
#include<vector>

using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> v(N+1, 0);
    vector<int> w(N+1, 0);
    for(int i=1; i<=N; i++) {
        cin >> v[i] >> w[i];
    }
    vector<vector<int>> dp(N+1, vector<int>(V+1, 0));
    // 状态转移
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=V; j++) {
            if(j >= v[i]) {
                // 注意这个地方的dp[i][j-v[i]] + w[i]是i而不是i-1，因为完全背包问题中，物品可以重复选择
                dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]]+w[i]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[N][V];
    return 0;
}

三、多重背包问题

多重背包问题指的是给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价值最高。每种物品的数量是有限的。

例题3.1 4.多重背包问题

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。第 i 种物品的体积是 $v_i$，价值是 $w_i$，数量是 $s_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。接下来有 N 行，每行三个整数 $v_i$,$w_i$,$s_i$，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围
$0<N, V≤1000$

$0<v_i, w_i≤1000$

$0<s_i≤1000$

输入样例

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

输出样例

9

解题思路

1. 定义状态：$f[i][j]$表示前i种物品放入容量为j的背包中所能获得的最大价值。
2. 状态转移方程：$f[i][j] = max(f[i-1][j], f[i][j-k*v[i]] + k*w[i])$，即k个第i种物品放入背包和不放入背包的最大值。
3. 初始化：$f[0][j] = 0$，$f[i][0] = 0$，表示背包容量为0或物品数量为0时，最大价值为0。
4. 遍历顺序：外层循环遍历物品，内层循环遍历背包容量，从小到大遍历。

代码实现

#include<iostream>
#include<vector>

using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> v(N+1, 0);
    vector<int> w(N+1, 0);
    vector<int> s(N+1, 0);
    for(int i=1; i<=N; i++) {
        cin >> v[i] >> w[i] >> s[i];
    }
    vector<vector<int>>> dp(N+1, vector<int>(V+1, 0));
    // 状态转移
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=V; j++) {
            for(int k=0; k<=s[i] && k*v[i] <= j; k++) {
                // 相当于将s[i]个物体中被选择的物体视为一个整体操作
                // 更像是01背包问题的变种
                dp[i][j] = max(dp[i][j], dp[i-1][j-k*v[i]] + k*w[i]);
            }
        }
    }
    cout << dp[N][V];
    return 0;
}

四、混合背包问题

混合背包问题指的是给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价值最高。每种物品的数量是有限的，有的物品可以无限次选择，有的物品只能选择一次。

例题4.1 7.混合背包问题

有 N 种物品和一个容量是 V 的背包。物品一共有三类：

• 第一类物品最多只能选择一件。
• 第二类物品可以无限制选择。
• 第三类物品最多只能选择若干件。

第 i 种物品的体积是 $v_i$，价值是 $w_i$，数量是 $s_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。接下来有 N 行，每行三个整数 $v_i$,$w_i$,$s_i$，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

• $s_i=−1$ 表示第 i 种物品只能用1次；
• $s_i=0$ 表示第 i 种物品可以用无限次；
• $s_i>0$ 表示第 i 种物品可以使用 $s_i$ 次。

输出格式

输出一个整数，表示最大价值。

数据范围
$0<N, V≤1000$

$0<v_i, w_i≤1000$

$-1<=s_i≤1000$

输入样例

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

输出样例

8

解题思路

1. 定义状态：$f[i][j]$表示前i种物品放入容量为j的背包中所能获得的最大价值。
2. 状态转移方程：根据物品的类型，选择不同的状态转移方程。
   • 如果是01背包问题，则$f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])$。
   • 如果是完全背包问题，则$f[i][j] = max(f[i-1][j], f[i][j-v[i]] + w[i])$。
   • 如果是多重背包问题，则$f[i][j] = max(f[i-1][j], f[i][j-k*v[i]] + k*w[i])$。
3. 初始化：$f[0][j] = 0$，$f[i][0] = 0$，表示背包容量为0或物品数量为0时，最大价值为0。
4. 遍历顺序：外层循环遍历物品，内层循环遍历背包容量，从小到大遍历。

代码实现

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

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> v(N+1, 0);
    vector<int> w(N+1, 0);
    vector<int> s(N+1, 0);
    for(int i=1; i<=N; i++) {
        cin >> v[i] >> w[i] >> s[i];
    }
    vector<vector<int>> dp(N+1, vector<int>(V+1, 0));

    for(int i=1; i<=N; i++) {
        if(s[i] == -1) {
            // 01背包
            for(int j=0; j<=V; j++) {
                dp[i][j] = dp[i-1][j]; // 不选
                if(j >= v[i]) {
                    dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]); // 选一次
                }
            }
        } else if(s[i] == 0) {
            // 完全背包
            for(int j=0; j<=V; 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]); // 可以重复选
                }
            }
        } else {
            // 多重背包
            for(int j=0; j<=V; j++) {
                dp[i][j] = dp[i-1][j]; // 不选
                for(int k=1; k<=s[i] && 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][V] << endl;
    return 0;
}

五、分组背包问题

分组背包问题指的是给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价值最高。每组物品 只能选择一个。

例题5.1 5.分组背包问题

有 N 组物品和一个容量是 V 的背包。每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 $v_{ij}$，价值是 $w_{ij}$，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。接下来有 N 组数据：

每组数据第一行有一个整数 $S_i$，表示第 i 个物品组的物品数量；每组数据接下来有 $S_i$ 行，每行有两个整数 $v_{ij}$, $w_{ij}$，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；

输出格式

输出一个整数，表示最大价值。

数据范围

$0<N,V≤100$

$0<S_i≤100$

$0<v_{ij},w_{ij}≤100$

输入样例

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

输出样例

8

解题思路

1. 定义状态：$f[i][j]$表示前i组物品放入容量为j的背包中所能获得的最大价值。
2. 状态转移方程：$f[i][j] = max(f[i][j], f[i-1][j-v_{ij}] + w_{ij})$，即选择第i组物品中的第j个物品和不选择第i组物品中的第j个物品的最大值。
3. 初始化：$f[0][j] = 0$，$f[i][0] = 0$，表示背包容量为0或物品数量为0时，最大价值为0。
4. 遍历顺序：外层循环遍历物品组，内层循环遍历背包容量，从小到大遍历。

代码实现

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, V;
    cin >> N >> V;
    vector<vector<int>> v(N+1);
    vector<vector<int>> w(N+1);
    for(int i=1; i<=N; i++) {
        int S;
        cin >> S;
        vector<int> vi(S+1, 0);
        vector<int> wi(S+1, 0);
        for(int j=1; j<=S; j++) {
            cin >> vi[j] >> wi[j];
        }
        // 加入
        v[i] = vi;
        w[i] = wi;
    }
    vector<vector<int>> dp(N+1, vector<int>(V+1, 0));
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=V; j++) {
            dp[i][j] = dp[i-1][j]; // 不选
            for(int k=1; k<v[i].size(); 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][V];
    return 0;
}