0-1背包
我比較熟悉，二維dp，通過觀察方程可以優(yōu)化成1維dp，不再贅述

完全背包
跟0-1背包的區(qū)別是每種型號的物品沒有限制，其實這樣反倒更簡單，用1維dp就可以，直接從第1個物品更新到最后一個物品(i)，然后從容量w[i]更新到容量C即可
直接轉(zhuǎn)載網(wǎng)友的代碼

#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 << "請輸入物品個數(shù):";
    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背包的區(qū)別在于，每個物品都有數(shù)量

思路：
把相同的物品看作不同的物品，這樣又變回了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 << "請輸入物品個數(shù):";
    cin >> n;
    cout << "請分別輸入" << n << "個物品的重量、價值和數(shù)量:" << endl; 
    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i] >> num[i];
    }
//進行問題轉(zhuǎn)換，把多重背包轉(zhuǎn)換成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的優(yōu)化思路：
0-1背包（二維數(shù)組、2行數(shù)組（%2取余）、1行數(shù)組（從右到左更新，因為dp狀態(tài)轉(zhuǎn)移時發(fā)現(xiàn)只跟上方和左方有關，跟右側無關，所以先更新右側不會影響左側的更新））
0-1背包變種
完全背包（只用1維dp即可，從第一個物品開始更新到最后1個物品，之后從容量1開始比較，更新到最大容量）
多重背包問題，每個物品有數(shù)量num[i]
多維費用背包問題，局限更多，比如體積和重量