背包问题
01背包
给你n个物品，价值分别为w，体积分别为v,求这些物品放入体积为V的背包可获得的最大价值。
-
对于每个物品，我们有两种选择，选这件物品，或不选，所以我们的状态就是，背包体积为j时的最大价值。
-
定义f[i][j]表示从1~i件物品选择剩余体积为j时的最大价值。对于上述两种决策，我们可以由上一阶段转移而来，即 不选f[i-1][j],选f[i-1][j-v[i]] 所以我们可以得到
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+value[i])
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
if(j<w[i])
f[i][j]=f[i-1][j];
else
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+value[i]);
}
}
通过观察我们发现，每一个状态i，都是由上一个i-1得到的，我们只用到了两层，并且这一层不影响上一层，所以我们可以省去第一维，这一层直接使用上一层的数据（滚动数组）
但这样的话，为了保证当前的状态仍由上一状态转移而来，对此我们需要考虑遍历顺序.
如果仍然正序遍历的话，那显然我们上一次的状态会被覆盖掉，所以我们考虑倒序遍历，从后面开始覆盖，不影响我们使用前面的数据。
那我们先遍历容量还是先遍历物品呢？
如果先遍历容量，再遍历物品，那么我们每次相当于只选择了一件物品，为什么呢？
假设我们外层循环到了j，而内层循环是从1~n，那么我们内层循环完，我们只选择了其中一种。
显然这样遍历是错误的。
所以我们需要调整顺序，先遍历容量后遍历物品，使每个容量都考虑了所有物品。
for(int i=1;i<=item.n;i++)
{
for(int j=bagsize;j>=w[i];j++)
{
if(j<w[i])
f[j]=f[j];
else
f[j]=max(f[j],f[j-w[i]]+value[i]);
}
}
完全背包
和01背包相比，只多了一个条件，即物品可以无限选取。
观察f[i][j - w[i]]和f[i][j]
f[i][j - w[i]] = max(f[i - 1][j - w[i]], f[i - 1][j - 2 * w[i]] + +value[i], f[i - 1][j - 3 * w[i]] + 2 * +value[i], .....)；
f[i][j]= max(f[i - 1][j], f[i - 1][j - w[i]] + value[i], f[i - 1][j - 2 * w[i]] + 2 * value[i], f[i - 1][j - 3 * w[i]] + 3 * value[i]);
将每一项一一比对，我们可以得到下列状态表示:
f[i][j] = max(f[i - 1][j], f[i][j - w[i]] +w)；
if(j<w[i]) f[i][j]=f[i-1][j];
else f[i][j]=max(f[i][j],f[i][j-w[i]]+val[i]);
优化：省去一维。
f[i][j] = max(f[i-1][j], f[i][j - weight[i]] + value[i])
用一维数组表示时
f[j] = max(f[j], f[j-weight[i]] + value[i]);
仔细观察原始状态方程可以发现，两者的状态方程差别在于max第二个参数
即max第一个参数依然为上个状态(上一个状态的f[i-1][j]仅用来服务当前状态的f[i][j], 不会影响当前行后面的状态)，但是第二个参数为本次状态，也就是说当前行的f[j]需要用到当前行的前面的结果，因此需要正序循环。
多重背包
相比完全背包，每种物品都有一定数量。
f[i][j]=max(f[i][j],f[i-1][j-k*w[i]]);
f[i][j]=max(f[i][j],f[i-1][j],f[i-1][j-w]+v,f[i-1][j-2w]+2v.....f[i-1][j-sw]+sv);
f[i][j-w]=max(f[i][j-w],f[i-1][j-w],f[i-1][j-2w]+v.........f[i-1][j-(s+1)w]+s*v);
发现两式差了一项，所以我们无法进行等价代换。
我们以旧可以当作01背包来做，我们可以考虑把所以物品都看作不同的单独的一个。有个很大的问题，就是复杂度。当然我们可以根据背包的体积做一些优化，比如当物品的数量很多并且超过了背包容量的时候，我们可以把超过容量的数量去掉，但是整体的复杂度还是很高。尤其是当我们背包容量很大的时候。 那怎么办呢？
二进制拆分优化多重背包
众所周知任何一个整数都可以用二进制表示，对于一个极大的十进制数，例如20亿以上的数，我们可以用一个32位的二进制表示，显然，数据被高效压缩。
换句话说每个十进制数都可以表示成32个数的累加
。
例如x可以表示为x=a[0]20+a[1]*21+a[2]2^2....(a[]表示每一位的系数0或1）。
对于一个函数f(a+b)=f(a)+f(b)我们直接求f(a+b)可能很困难，但我们可以很轻松的算出f(a),f(b)这些子状态，我们用二进制累加起来就可以解决。
对于多重背包来说，我们可以把每种物品的个数拆成若干二进制数，打包，即将其代价和收益累加起来，看作一件物品，那么我们就可以把问题转化成01背包。
//二进制拆分
for(int i=0;i<=32;i++)
{
int cur=1<<i;
if(n<cur)
{
cout<<n<<endl;
break;
}
else
{
n-=cur;
cout<<cur<<endl;
}
}
单调队列优化多重背包
dp[m] = max(dp[m], dp[m-v] + w, dp[m-2v] + 2w, dp[m-3v] + 3w, ...)
接下来，我们把 dp[0] --> dp[m] 写成下面这种形式
dp[0], dp[v], dp[2v], dp[3v], ... , dp[k*v]
dp[1], dp[v+1], dp[2v+1], dp[3v+1], ... , dp[k*v+1]
dp[2], dp[v+2], dp[2v+2], dp[3v+2], ... , dp[k*v+2]
...
显而易见，m 一定等于 kv + j，其中 0 <= j < v
所以，我们可以把 dp 数组分成 j 个类，每一类中的值，都是在同类之间转换得到的
也就是说，dp[kv+j] 只依赖于 { dp[j], dp[v+j], dp[2v+j], dp[3v+j], ... , dp[k*v+j] }
因为我们需要的是{ dp[j], dp[v+j], dp[2v+j], dp[3v+j], ... , dp[k*v+j] } 中的最大值，
可以通过维护一个单调队列来得到结果。这样的话，问题就变成了 j 个单调队列的问题
所以，我们可以得到
dp[j], dp[v+j], dp[2v+j], dp[3v+j], ... , dp[k*v+j]
但是，这个队列中前面的数，每次都会增加一个 w ，所以我们需要做一些转换
dp[j] = dp[j]
dp[j+v] = max(dp[j], dp[j+v] - w) + w
dp[j+2v] = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w) + 2w
dp[j+3v] = max(dp[j], dp[j+v] - w, dp[j+2v] - 2w, dp[j+3v] - 3w) + 3w
...
这样，每次入队的值是 dp[j+kv] - kw
单调队列问题，最重要的两点
1）维护队列元素的个数，如果不能继续入队，弹出队头元素
2）维护队列的单调性，即：尾值 >= dp[j + kv] - kw
本题中，队列中元素的个数应该为 s+1 个，即 0 -- s 个物品 i
分组背包
物品被分为了不同组，从每组中至多选一个物品，使收益最大。
我们设f[i][j]为当前考虑到了第i组物品，剩余容里为j的背包能装物品的最大价值，那么很容易想到我们需要去枚举第i组物品，考虑选哪一个物品时最优的(选或者不选)，状态转移方程就是
if(j>=v[i][k]) f[i][j]=max(f[i][j],f[i−1][j−v[i][k]]+w[i][k]),v[i][k]和w[i][k]分别表示第i组物品中第k个物品的体积和价值。
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=1;k<=s[i];k++)//s[i]表示第i组物品的个数
if(j>=v[i][k])//剩余的背包容量j大于第i组的第k个物品的体积
{
f[i][j] = max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}
混合背包
顾名思义，物品有多类。
只能用1次（01背包）
可以用无限次（完全背包）
最多只能用s[i]次（多重背包）
那怎么办呢？for循环里直接分类？数据范围稍稍大一点那不就完蛋了吗？不妨思考将其转化为一类。
对于01背包物品其数量为1，完全背包的数量为总体积/物品体积**，所以我们将混合问题成功转换成了多重背包，配合二进制、单调队列优化食用更佳。
二维费用背包问题
直接加一维，结束。
更新中。。。。
标签：2v,背包,max,问题,物品,我们,dp From： https://www.cnblogs.com/mrkou/p/16770506.html