模板

DP问题划分依据： 从 最后一步 划分, 且每个状态的最后一步不同 除了完全背包问题, 其余所有背包问题优化到1维之后都是从大到小循环

for 物品
	for 体积
		for 决策

完全背包：求所有前缀的最大值 多重背包：求滑动窗口的最大值

01 背包

未一维优化

int main()
{
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
            if(v[i] > j) f[i][j] = f[i - 1][j];
            else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
    cout << f[n][m] << endl; 
}

一维优化

int main()
{
    for(int i = 1; i <= n; i++) 
    {
        for(int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
    printf("%d\n",f[m]);
}

完全背包

朴素

int main()
{
    cin >>n ;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for(int i = 1; i < =n ;i ++)
        for(int j = 0; j <= m; j++)
            for(int k = 0; k * v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
    cout << f[n][m] << endl;
}

优化k

int main()
{
    cin >> n;
    for(int i = 1; i <=n ;i++) cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if(v[i] <= j)
                f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }
    cout << f[n][m] << endl;
}

化成一维

int main()
{
    cin >> n;
    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;
}

多重背包

数据范围小

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;
}

数据范围大

体积和物品数小于2000时

用 2^n(n = 0,1,2,3,…,k)(2^k+1 > s) 分组，为什么说少了很多组却仍能得到正确结果呢？ 因为当你枚举到 选 3 个物品时，前面已经枚举过的 选1 和 选2 可以组成 选3， 也就是说 选1 和 选2 的结果跟你 选3 是等价的， 那么我们就可以把 选3 优化掉不去枚举。

怎么跟 01 背包问题扯上关系呢？ 你划分之后的物品可以抽象成 “新” 的物品 [打包的物品] (s) (s s) (s s s s ) ( s s s s…) … [对应] 1 2 4 8 … 那么对每个新物品做01背包，便能求出正解。 对于 选3 (s s s)，可以由选择过 选1 和 选2 的状态表示，同样 选5 也能由 更小的状态表示出来

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 25000, M = 2010; // N = 1000 * log 2000 (物品种类数 * log 每种物品的个数)
int n,m, cnt; // cnt 将每种物品二进制展开后的数组下标
int v[N],w[N];
int f[M]; // 01背包的一维优化
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        int k = 1;
        while(k  <= c)
        {
            v[++cnt] = a * k;
            w[++cnt] = b * k;
            c -= k;
            k *= 2;
        }
        if(c > 0) // 最后的那个 c
        {
            v[++cnt] = a * c;
            w[++cnt] = b * c;
        }
    }
    int n = cnt;
    for(int i = 1; i <= cnt; i++)
        for(int j = m; j >= v[i]; i--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m];
    return 0;
}

体积和物品数小于20000时

状态表示依然是前i个物品, 背包体积为j的最大价值。 划分为当前i物品选 0, 1, 2, 3,,, s个

f[i][j] = 
            f[i-1][j],     f[i-1][j-v]+w,   f[i-1][j-2v]+2w,,,f[i-1][j-sv]+sw}
f[i][j-v]= 
            f[i-1][j-v],   f[i-1][j-2v]+w,  f[i-1][j-3v]+2w,,,f[i-1][j-sv]+(s-1)w, f[i-1][j-(s+1)v]+sw}
f[i][j-2v]=
            f[i-1][j-2v],  f[i-1][j-3v]+w,  f[i-1][j-4v]+2w,,,f[i-1][j-sv]+(s-2)w, f[i-1][j-(s+1)v]+(s-1)w, f[i-1][j-(s+2)v]+sw}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e4 + 10;
int n,m;
int q[N], g[N], f[N];
const int V[] = {1,2,3,4};
const int W[] = {2,4,4,5};
const int S[] = {3,1,3,2};
int main()
{
    //cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        int v = V[i],w = W[i],s = S[i];
        cin >> v >> w >> s;
        memcpy(g, f, sizeof f);
        for(int r = 0; r < v; r++)
        {
            int hh =0, tt = -1;
            for(int j = r; j <= m; j += v)
            {
                if(hh <= tt && q[hh] < j - s*v) hh++;
                if(hh <= tt) f[j] = max(f[j], g[q[hh]] + (j - q[hh]) / v * w);
                while(hh <= tt && g[q[tt]] - (q[tt] - r)/v*w <= g[j] - (j - r)/v * w)tt--;
                q[++tt] = j;
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}

分组背包

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> s[i];
        for(int j = 1; j <= s[i]; j++)
        {
            cin >> v[i][j] >> w[i][j];
        }
    }
 
    for(int i = 1; i <= n; i++)
    {
        for(int j = m; j >= 0; j--)
            for(int k = 1; k <= s[i]; k++)
                if(v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    }
    cout << f[m];
    return 0;
}