经典模型

y氏DP

状态表示
$f(i,j)$表示状态，有两个限制条件：只从前i个选，体积<j；

状态计算
状态计算一般对应集合的划分，遵循不重不漏的原则

DP优化
对状态转移方程进行等价变形

01背包问题

体积为V，价值为W，每件物品只能用1次，使价值最大；

void solve(){
    for (int i=1;i<=n;i++)
    {
        for (int j =1 ;j<=m;j++)
        {
            f[i][j] = f[i-1][j];//if判断是否越界
            if (j>=v[i]) f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<f[n][m];
}
int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>v[i]>>w[i];
    solve();
}
void solve(){//滚动数组优化
    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]);
    cout<<f[m];
}

完全背包问题

朴素做法有三重循环，时间复杂度较高；优化如下；

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

还能再优化

void solve(){
    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];
}

最终01背包逆序循环，完全背包顺序循环，这是唯一的不同。

多重背包问题

不能像完全背包问题一样优化，物品数量有了上限，会导致每个式子的结尾不能对齐，应该使用二进制优化。
二进制优化就是用二进制表示某一范围的任意数，将物品数量打包为1,2,4,..

int main()
{
    cin>>n>>m;
    int cnt=0;//将多重背包问题二进制转换为01背包
    for (int i=1;i<=n;i++) 
    {
        int a,b,s;
        cin>>a>>b>>s;
        int k = 1;
        while(k<=s)
        {
            cnt++;
            v[cnt] =  a * k, w[cnt] = b*k;
            s -= k;
            k *= 2;
        }
        if (s>0)
        {
            cnt++;
            v[cnt] = a*s, w[cnt] = b*s;
        }
    }
    n = cnt;
    solve();//01背包代码
}

分组背包问题

第i组一个都不拿，第i组拿第k个

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, V = 110, S=110;
int n,m;
int f[N][N],v[N][N],w[N][N],s[N];

void solve(){//朴素版
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j<=m; j++ )
        {
            f[i][j] = f[i-1][j];
            for (int k=1;k<=s[i];k++)
            {

                if (j>=v[i][k]) f[i][j] = max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
            }
        }
    cout<<f[n][m];
}

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];
        }
    }
    solve();
}
void solve(){//优化版
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j>=0; j-- )
            for (int k=1;k<=s[i];k++)
              if (j>=v[i][k]) f[j] = max(f[j],f[j-v[i][k]]+w[i][k]);
    cout<<f[m];
}