各种背包问题

0-1背包
我比较熟悉，二维dp，通过观察方程可以优化成1维dp，不再赘述

完全背包
跟0-1背包的区别是每种型号的物品没有限制，其实这样反倒更简单，用1维dp就可以，直接从第1个物品更新到最后一个物品(i)，然后从容量w[i]更新到容量C即可
直接转载网友的代码

#include <iostream>
#define V 500
using namespace std;
int weight[20 + 1];
int value[20 + 1];
int f[V + 1];
int max(int a, int b) {
    return a > b ? a : b;
}
int main() {
    int n, m;
    cout << "请输入物品个数:";
    cin >> n;
    cout << "请分别输入" << n << "个物品的重量和价值:" << endl; 
    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i];
    }
    cout << "请输入背包容量:";
    cin >> m;
    for (int i = 1; i <= n; i++) {//选中第i件物品
        for (int j = weight[i]; j <= m; j++) {//遍历放入第i件物品后的最大价值，直接从w[i]开始考虑
            f[j] = max(f[j], f[j - weight[i]] + value[i]);
        }
    }
    cout << "背包能放的最大价值为:" << f[m] << endl;
}

多重背包问题
与0-1背包的区别在于，每个物品都有数量

思路：
把相同的物品看作不同的物品，这样又变回了0-1背包问题

代码：

#include <iostream>
using namespace std;
#define V 1000
int weight[50 + 1];
int value[50 + 1];
int num[20 + 1];
int f[V + 1];
int max(int a, int b) {
    return a > b ? a : b;
}
int main() {
    int n, m;
    cout << "请输入物品个数:";
    cin >> n;
    cout << "请分别输入" << n << "个物品的重量、价值和数量:" << endl; 
    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i] >> num[i];
    }
//进行问题转换，把多重背包转换成0-1背包
    int k = n + 1;
    for (int i = 1; i <= n; i++) {
        while (num[i] != 1) {
            weight[k] = weight[i];
            value[k] = value[i];
            k++;
            num[i]--;
        }
    }
    cout << "请输入背包容量:";
    cin >> m;
    for (int i = 1; i <= k; i++) {
        for (int j = m; j >= 1; j--) {
            if (weight[i] <= j) f[j] = max(f[j], f[j - weight[i]] + value[i]);
        }
    }
    cout << "背包能放的最大价值为:" << f[m] << endl;
}

最后简单说一下dp的优化思路：
0-1背包（二维数组、2行数组（%2取余）、1行数组（从右到左更新，因为dp状态转移时发现只跟上方和左方有关，跟右侧无关，所以先更新右侧不会影响左侧的更新））
0-1背包变种
完全背包（只用1维dp即可，从第一个物品开始更新到最后1个物品，之后从容量1开始比较，更新到最大容量）
多重背包问题，每个物品有数量num[i]
多维费用背包问题，局限更多，比如体积和重量