https://blog.csdn.net/yandaoqiusheng/article/details/84782655

1. 0-1背包

將件體積為崔列，價值為的物品放入體積為的背包中宰闰，求價值和的最大值彻犁。
開一個大小為的數(shù)組械姻，問題轉(zhuǎn)化為求。
先對初始化：

for (int j = 1; j <= V; j++) {
        if (w[1] <= j) dp[j] = v[1];///說明此時可以放進第一個物品
    }

再用滾動數(shù)組：

for (int i = 2; i <= N; i++) {
        for (int j = V; j >= 1; j--) {
            if (w[i] <= j) dp[j] = max(dp[j], dp[j - w[i]] + d[i]);
        }

可以精簡成：

for (int i = 1; i <= N; i++)//從1開始遍歷倦挂，省去了初始化邊界，下同
        for (int j = V; j >= w[i]; j--)
            dp[j] = max(dp[j], dp[j - w[i]] + d[i]);

關(guān)于初始化：
若題目要求“恰好裝滿背包”担巩，將設(shè)為0方援，其它設(shè)為-1。
若沒有要求涛癌，則全部設(shè)為0犯戏。

2.完全背包

有種物品和一個容量為的背包，每種物品都有無限件可用拳话。第種物品的費用是先匪，價值是。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量弃衍，且價值總和最大呀非。

類比0-1背包問題，顯然有狀態(tài)轉(zhuǎn)移方程：

只需要枚舉滿足條件的即可镜盯，不停地取最大值即可岸裙。

優(yōu)化：

for (int i = 1; i <= N; i++)
    for (int j = w[i]; j <= V; j++)
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

就是把0-1背包問題中的第二層循環(huán)由倒序遍歷改為順序遍歷，因為物品有無窮多個速缆，所以生成新的價值時要利用已經(jīng)更新的價值降允。
證明：
用代替中的，得

對于固定的艺糜，是定值剧董，可以提到最大值運算的外面，得

令倦踢，得

移項送滞，得

比較上式和的右邊侠草，發(fā)現(xiàn)只差范圍中的情況辱挥，所以

由此遞推式容易發(fā)現(xiàn)，對于边涕，必須用到已經(jīng)更新的狀態(tài)晤碘，證明結(jié)束褂微。

3.多重背包

https://www.luogu.org/problem/P1776
有種物品和一個容量為的背包。第種物品最多有件可用园爷，每件體積是宠蚂，價值是。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量童社，且價值總和最大求厕。
相當(dāng)于有界的完全背包問題。
同理完全背包問題扰楼，可以得到狀態(tài)轉(zhuǎn)移方程：

其中呀癣，且。
由此可以得到代碼：

#include<iostream>
#include<algorithm>
using namespace std;
int n, maxw;
int dp[40010], v[100010], w[100010], m[100010];
int res;
int d, s, k;
int main() {
    cin >> n >> maxw;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i] >> m[i];
    }
    for (int i = 1; i <= maxw; i++)  
        dp[i] = (i / w[1] <= m[1]) ? (i / w[1]) * v[1] : m[1] * v[1];
    for (int i = 2; i <= n; i++) {
        for (int j = maxw; j >= 1; j--) {
            for (int k = 0; k <= m[i]; k++) {
                if (j < k * w[i]) break;
                dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]);
            }
        }
    }
    cout << dp[maxw];
    return 0;
}

時間復(fù)雜度：
由數(shù)據(jù)范圍弦赖，是數(shù)量級项栏，會超時。
單調(diào)隊列優(yōu)化：
首先變換狀態(tài)轉(zhuǎn)移方程：設(shè)為除以的商（向下取整）蹬竖，為除以的余數(shù)沼沈，令，有：

在此方程中币厕，和都是定值列另，只有是變量。
注意到旦装，由轉(zhuǎn)移而來计盒，即及其后面共個狀態(tài)轉(zhuǎn)移到蛤奥，而及其后面共個狀態(tài)轉(zhuǎn)移到...即每次轉(zhuǎn)移都是個連續(xù)狀態(tài)轉(zhuǎn)移到它們前面的那個狀態(tài)。
聯(lián)想到滑動窗口，這是一個連續(xù)區(qū)間的最值問題禾酱，可以用單調(diào)隊列！
算法：
邊讀入邊做资厉，從到枚舉泄朴，對于每一個，維護一個對單減的隊列棒妨，并儲存每個元素的值踪古。
從進隊，保證隊首元素是目前遍歷的所有元素中最大的券腔。當(dāng)隊首元素的下標(biāo)和要進隊的元素的下標(biāo)差大于時伏穆，隊首元素出隊。最后將要進隊元素對應(yīng)的dp值和現(xiàn)在的隊首元素取最大纷纫。

#include<iostream>
#include<algorithm>
using namespace std;
int n, maxw;
int v, w, m;
int ans;
struct T {
    int num;
    int val;
}q[100010];
int head, tail;
int dp[100010];
int now;
int main() {
    cin >> n >> maxw;
    for (int i = 1; i <= n; i++) {
        cin >> v >> w >> m;
        for (int d = 0; d < w; d++) {
            head = 1, tail = 0;
            for (int s = 0; d + s * w <= maxw; s++) {
                now = d + s * w;
                while (head <= tail && dp[now] - v * s >= q[tail].val) tail--;
                q[++tail].val = dp[now] - v * s;
                q[tail].num = s;
                if (s - q[head].num > m) head++;
                dp[now] = max(dp[now], q[head].val + v * s);
            }
        }
    }
    cout << dp[maxw];
    return 0;
}

幾點說明：
1.雖然看上去是三重循環(huán)枕扫，但是由于對做了剩余類劃分，實際上只對遍歷了一次辱魁，時間復(fù)雜度為烟瞧。
2.分清楚：存的是诗鸭，單調(diào)隊列存的是，比較的時候要参滴，賦值的時候要强岸。
3.這種方法可以用于

狀態(tài)壓縮
把原問題轉(zhuǎn)化為有個物品的0-1背包，時間復(fù)雜度仍是砾赔，沒什么改進蝌箍，但是如果把第種物品分成若干組，每組有個物品暴心，容易證明0到的任何一個數(shù)都可以寫成若干組的和十绑。這種方法可以把時間復(fù)雜度降到。

#include<iostream>
#include<algorithm>
using namespace std;
int n, maxw;
int v, w, m;
int ans;
int num;
int dp[100010];
int main() {
    cin >> n >> maxw;
    for (int i = 1; i <= n; i++) {
        cin >> v >> w >> m;
        num = min(m, maxw / w);
        for (int k = 1; num; k <<= 1) {
            if (k > num) k = num;//注意不是num=k
            num -= k;
            for (int j = maxw; j >= w * k; j--) {
                dp[j] = max(dp[j], dp[j - w * k] + v * k);
            }
        }
    }
    cout << dp[maxw];
    return 0;
}

這個方法沒有第一種優(yōu)秀酷勺，但是好寫本橙，而且可以用于混合背包（0-1，完全脆诉，多重都有）甚亭，只要把完全背包的設(shè)成即可。
https://www.luogu.org/problem/P1833（最后一組測試數(shù)據(jù)有一個19:8）
注意：這種時間的讀寫击胜，用scanf("%d:%d %d:%d")亏狰，不要用cin.get()！

4.二維費用背包

對于每件物品偶摔，具有兩種不同的費用暇唾；選擇這件物品必須同時付出這兩種代價；對于每種代價都有一個可付出的最大值（背包容量）辰斋。問怎樣選擇物品可以得到最大的價值策州。設(shè)這兩種代價分別為代價1和代價2，第件物品所需的兩種代價分別為和宫仗。兩種代價可付出的最大值（兩種背包容量）分別為和够挂。物品的價值為。
和一維一樣藕夫，有狀態(tài)轉(zhuǎn)移方程：
孽糖。
代碼：

for (int i = 1; i <= n; i++)
    for (int j = V; j >= w[i]; j--)
        for (int k = T; k >= g[i]; k--)
            f[j][k] = max(f[j][k], f[j - w[i]][k - g[i]] + v[i]);

推論：所取物體的總個數(shù)不超過的一維背包，可以看作另外一維費用是件數(shù)的二維背包毅贮，每個物品的件數(shù)費用都是1办悟，件數(shù)的最大值為。

5.分組背包

有件物品和一個容量為的背包滩褥。第件物品的費用是病蛉，價值是。這些物品被劃分為若干組，每組中的物品互相沖突铡恕，最多選一件。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量丢间，且價值總和最大探熔。
設(shè)為前組物品在背包容量為的約束下的最大價值和，則：
i烘挫。
代碼：

    for (int i = 1; i <= n; i++)//遍歷所有的組
        for (int j = m; j >= 0; j--)
            for (int k = 1; k <= j; k++)//k<=j防止數(shù)組越界
                f[j] = max(f[j], f[j - k] + a[i][k]);