第一行两个整数，NNN，VVV，用空格隔开，分别表示物品数量和背包容积。 接下来有 NNN 行，每行两个整数 vi,wiv_i,w_ivi,wi，用空格隔开，分别表示第 iii 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0 0
输入样例
4 5 1 2 2 4 3 4 4 5
输出样例
8
具体实现
1. 实现思路
01 背包问题的集合划分是一种非常经典的划分方法，可整体划分为两部分，不包含 iii 和包含 iii。
不包含 iii 可以理解为，从 1到i−11到i-11到i−1 当中选取物品，总体积不大于 jjj，该集合的最大值就是 f(i−1,j)f(i-1,j)f(i−1,j)。
包含 iii 可以理解为，从 1到i1到i1到i 当中选取物品，总体积不大于 jjj，该集合的最大值直接求取的困难很大，我们可以曲线救国，先将所有选法当中的第 iii 个物品去掉（最大的那部分是依旧是最大的），便转换为从 1到i−11到i-11到i−1 当中选取物品，总体积不大于 j−vij-v_ij−vi，此时所有选法的最大值就是 f(i−1,j−vi)f(i-1,j-v_i)f(i−1,j−vi)，但由于我们去掉过第 iii 个物品，因此，原本的最大值就是 f(i−1,j−vi)+wif(i-1,j-v_i)+w_if(i−1,j−vi)+wi。
第一行两个整数，NNN，VVV，用空格隔开，分别表示物品种数和背包容积。 接下来有 NNN 行，每行两个整数 vi,wiv_i,w_ivi,wi，用空格隔开，分别表示第 iii 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0 0
输入样例
4 5 1 2 2 4 3 4 4 5
输出样例
10
具体实现
1. 实现思路
完全背包问题和 01 背包问题的区别在于完全背包问题当中的物品可以被选择无数次。
完全背包问题可以选择使用一维或二维进行解决，如果直接使用与 01 背包问题相同的方法是三个 for 循环，此时会超时，就需要进行优化。
那么，f[i]f[i]f[i] 就表示体积是 iii 的情况下，最大价值是多少（状态表示）。
f[0……m]f[0……m]f[0……m] 当中的最大值就是我们所求的结果。
2. 实现代码
#include using namespace std;const int N = 1010;//n, m表示物品数量和背包体积
int n, m;
//v[N], w[N]表示物品的体积和价值
int v[N], w[N];
//f[N]表示总价值
int f[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 ++ ){f[j] = max(f[j], f[j - v[i]] + w[i]);}}cout << f[m] << endl;return 0;
}
第一行两个整数，NNN，VVV，用空格隔开，分别表示物品种数和背包容积。 接下来有 NNN 行，每行三个整数 vi,wi,siv_i,w_i,s_ivi,wi,si，用空格隔开，分别表示第 iii 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
0 0
输入样例
4 5 1 2 3 2 4 1 3 4 3 4 5 2
输出样例
10
具体实现
1. 实现思路
多重背包问题与上述两种背包问题的区别在于每个物品最多有 sis_isi 个。
此题与 01 背包问题基本相同。
2. 实现代码
#include using namespace std;const int N = 110;//n, m表示物品种数和背包体积
int n, m;
//v[N], w[N]，s[N]表示物品的体积，价值，数量
int v[N], w[N], s[N];
//f[N][N]表示价值
int f[N][N];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] && 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;return 0;
}
