多重背包

int w[maxn], v[maxn]; //w[i] 代表第 i 种物品价值 v[i] 代表体积

int f[maxn][maxm]; //前 i 种物品用了 j 的体积所能得到的最大价值

int cnt = 0; //总共拆成了多少个物品
for (int i = 1; i <= n; ++i)
{
int w, u, v;// 价值，个数，体积
cin >> w >> v >> u;
int k = 1; //先拆一个
while (u >= k)
{
++cnt;
:: w[cnt] = w * k;
:: v[cnt] = v * k;
u -= k;
k *= 2;
}
if (u != 0)
{
++cnt;
:: w[cnt] = w * u;
:: w[cnt] = v * u;
}
}
//再做一边 01背包
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j <= m; ++j)
{
f[i][j] = f[i - 1][j];
if (j - v[i] >= 0) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}