比01背包和完全背包难一点的有：多重背包和混合背包。
无忧化多重背包
P1776
这道题目不用优化过不了，但是我们可以先来讲一下没优化的多重背包。
我们只要在01背包的基础上加一重循环枚举选多少个就可以了。
时间复杂度： v\times \displaystyle\sum_{i=1}^{n}{s_i} 。
核心代码如下（ s_i 表示这个物品有多少个）
for(int i=1;i<=n;++i)
for(int j=v;j>=w[i];++j)
for(int k=1;k<=s[i];++k)
if(w[i]*k>=j) dp[j]=max(dp[j],dp[j-w[i]*k]+c[i]*k);
二进制拆分优化多重背包
什么是二进制拆分？
举个例子 13 可以拆成 1,2,4,5 。
1,2,4,6 可以组成 0 ~ 13 的任何数字。
怎么拆呢？
其实就是拆成总和小于等于他的 2 的幂次（ 1,2,4 ），和数字减去刚刚拆的总和（ 6 ）。
那么我们将所有物品进行二进制拆分，然后进行01背包即可。
时间复杂度： v\times \displaystyle\sum_{i=1}^{n}{log s_i} 。
拆分物品的代码如下（p是最终物品个数）
int x,y,s,k=1;
cin>>x>>y>>s;
while(1)
{
if(s<k) break;
s-=k;
p++;
w[p]=x*k,c[p]=y*k;
k*=2;
}
if(s) p++,w[p]=x*s,c[p]=y*s;
混合背包
P1833
其实很简单，两种方法。
1. 将完全背包的数量无限看成数量为 v 。
2. 将完全背包特殊处理（正序遍历进行dp），多重背包倒序dp。