背包问题(Knapsack Problem)简介(Introduction)背包问题(Knapsack problem) 是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价位，在限定的总重量内，我们怎么选择，才能促使物品的总价钱最高。问题的名称来源于怎么选择最合适的物品放置于给定挎包中。相似问题常常出现在商业、组合物理，计算复杂性理论、密码学和应用数学等领域中。
也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkle和Hellman提出的。描述(Description)
简单来说，背包问题就是在重重限制条件下求最值问题。
至于谈到的NP完全问题，又称作方程复杂程度的非确定性问题，反正晓得处理上去很麻烦。就像求解一个很大的素数，我们只能一点一点猜想，并没有办法说能否通过某种运算直接确定当前素数前面一个素数是谁。
分析(Analysis)
背包问题是典型的动态规划(Dynamic Programming) 问题。
而动态规划问题有这样的性质：
既要考虑到问题所有的可能性，同时保证正确性，还要保存下中间的结果以保证效率。动态规划要求能把整个问题的解分成好多个子问题的解，其中最为重要的就是建立问题之间的关系(状态转移方程)。
动态规划问题须要具备最优子结构的性质。
通常情况下，解决动态规划问题，最重要的是：
描述最优子结构。找到递归定义的最优解。
基于这两点，就可以通过递归求得最优解。
常见的背包问题分为以下几种：
01背包问题 有N件物品和一个容量是V的挎包。每件物品只能使用一次。 第i件物品的容积是v_i，价值是w_i。
求解将什么物品放入挎包，可使那些物品的总容积不超过挎包容量，且总价值最大。分析(Analysis)
对于01挎包问题，我们很自然的有质朴的做法，即DFS。由于每一个物品只有两种状态，选和不选，因此最终呈现的时间复杂度就是O(2^n)，显然对于稍大一点点的数据都会超时。而挎包本身的状态又物品数和自身容量决定，相对来说状态数少了好多。而且可以得到递推关系。
我们把原先所有的物品人为编号为1\sim n，并且假定最终的最优结果为挎包中倒入了x个物品。
假设当处理到第i个物品，背包容量为j时，对应的最大的价值为V_{ij}。
如上面剖析的，每一个状态又物品数和容量大小来表示，不妨使用一个二维数组来表示，即V_{ij} =V[i][j]。那么背包问题的最优解为V[N][V]。(这里指递归到N和V时的情况，并不是指所有的物品都选而且正好放满)也就是说V[N][V]是最终答案。
假设这么对于i-1时的情况，我们早已晓得了挎包容量为0\sim j时的最大值(V[i-1][0]\sim V[i - 1][j]已知)。那么处理序号为i而且挎包容量为j时的最大价值时，有两种可能：
当前挎包容量j大于i号物品的容积v_i,那么第i号物品就难以装入挎包(那就不放)，有V[i][j] = V[i-1][j]。与前面相反，能装入第i号物品，我们须要考虑的是前一状态更新后的总价值是否小于当前总价值，即V[i-1][j - v_i]+w_i是否小于V[i][j]。如果小于，则更新：V[i][j] = V[i-1][j-v_i]+w_i，否则就不倒入，即V[i][j] = V[i-1][j]。
由此我们就找到了求最优子结构的办法。下面须要做的是找寻递归的状态转移方程。由上面的剖析，最优解正好就是由最优子结构递归来的。有：
V[i][j]=max \begin{cases} V[i-1][j],j< v[i]\\ V[i-1][j-v_i]+w[i],j\ge v[i]\\ \end{cases} \\
因此我们有质朴的代码：
int v[N],w[N];
int f[N][N];
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 -1][j - v[i]] + w[i]);
}
通过观察我们可以发觉：V[i][j]中的第一项i一定是由前一项i-1带来的。由数据储存方法我们不难想到：可以去除[i]那一维。相当于用当前i组覆盖之前i-1组。优化后发觉f[i][j] = f[i-1][j]变为f[j]= f[j]可以直接去除。因此代码优化为：
int v[N],w[N];
int f[N];
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]);
//f[i][j] = f[i - 1][j];
//if(j >= v[i])
}
但是这个代码是存在错误的，我们可以使用覆盖的方法带省去i这一维，但是因为j从v[i]循环到m，计算f[j]时，f[j-v[i]]事实上是f[i][j-v[i]]而不是我们须要的f[i-1][j-v[i]](换句话说，用于j从小到大递增，导致在求f[i][j]时，由于缺乏了i这一维度，f[i - 1][j-v[i]]已经被更新为f[i][j-v[i]])。
解决方法也很简单，不让它先被更新即可，那么把j的从小打大循环改为从大到小。因此有：
int v[N],w[N],f[N];
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]);
其实这儿还可以在读入 v[i],w[i] 时候更新 f[j] 这样还可以优化掉一点空间。
完全挎包问题 有N种物品和一个容量是V的挎包，每种物品都有无限件可用。
第i种物品的容积是v_i，价值是w_i。
求解将什么物品放入挎包，可使那些物品的总容积不超过挎包容量，且总价值最大。
完全挎包问题和01背包问题十分相像，区别仅在于：01挎包的物品只有选和不选两种情况。而完全挎包的物品选几个和不选这样的情况。我们不难想到相应的状态转移方程：
V[i][j] = max \begin{cases}V[i-1][j],j< v[i] \\V[i-1][j-kv[i]]+kw[i],kv[i]\le j,1\le k \end{cases}\\
其中k表示枚举的第i个物品的个数。k=0时就是不选。
因此朴实做法为：
int v[N],w[N];
int f[N][N];
for(int i = 1; i <= n ; i++)
for(int j = 1; 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]);
三重循环效率很低，考虑优化。优化最好处理的就是最外层的k。我们把k的循环展开，有：f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2\times v[i]]+2\times w[i],f[i-1][j-3\times v[i]]+3 \times w[i]\cdots )
而： f[i][j-v[i]] = max(f[i-1][j-v[i]],f[i-1][j-2\times v[i]]+w[i],f[i-1][j-3\times v[i]]+2\times w[i]\cdots)
对比两式，我们可以发觉，f[i][j]可以和k无关：f[i][j] = max(f[i-1][j],f[i][j-v[i]]+w[i]\\
int v[N],w[N];
int f[N][N];
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]);
}
我们发觉，优化后的完全挎包代码和01挎包朴实代码十分相像，一点区别就在01挎包的f[i-1][j-v[i]]改为了完全挎包的f[i][j-v[i]]。
也就是说01挎包都是从i-1层转移过来的，而完全挎包是从第i层转移过来的。我们还可以和01挎包做类似的聚类操作。
int v[N],w[N],f[N];
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]);
如上面所讲的，由于01背包改动时，我们须要的f[i-1][j-v[i]]会因为j的从小到大更新而变为f[i][j-v[i]]。而正好，完全挎包的状态转移方程就是此式。因此不用像01挎包一样把j的循环次序倒置。
多重背包问题 有N种物品和一个容量是V的挎包。
第i种物品最多有s_i件，每件容积是v_i，价值是w_i。
求解将什么物品放入挎包，可使物品容积总和不超过挎包容量，且价值总和最大。
多重背包问题可视为介于完全挎包问题和01背包问题的问题。物品既不是只有一件，又不是有无穷件，而是有指定件。
我们可以由完全挎包的递推关系增设上限来得到多重背包问题的地推关系：
V[i][j] = max \begin{cases} V[i-1][j],j< v[i] \\ V[i-1][j-kv[i]]+kw[i],kv[i]\le j,1\le k \le s[i]\\ \end{cases}\\
我们自然可以得到朴实多重挎包的代码：
int v[N],w[N];
int f[N][N];
for(int i = 1; i <= n ; i++)
for(int j = 1; j <= m ;j++)
for(int k = 0; k*v[i] <= j && k<=s[i];k++)
f[i][j] = max(f[i][j],f[i - 1][j - k*v[i]] + k*w[i]);
}
我们故技重施，尝试使用完全挎包的优化方式优化多重挎包：
f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2\times v[i]]+2\times w[i]\cdots f[i-1][j-s[i]\times v[i]]+s[i] \times w[i])
而： f[i][j-v[i]] = max(f[i-1][j-v[i]],f[i-1][j-2\times v[i]]+w[i]\cdots f[i-1][j-s[i]\times v[i]]+(s[i]-1)\times w[i])
最后还多一项:+f[i-1][j-(s[i]+1)\times v[i]] + s[i]\times w[i](由于完全挎包没有数目的限制，最后不会多下来一项，才能消地彻底。) 因为我们难以求出相同的部份的max值，所以我们难以直接通过这些优化方法来优化多重挎包。
但是有一个神奇的优化方法：2补码优化。 我们把物品以2进制方式“打包”(1,2,4,8,16……)，需要s[i]个物品时，我们挑整个“包”。我们把O(n)的做法优化为O(logn)级别。
对于s[i]个物品，我们依次打第一个包(里面放1件)、第二个包(里面放2件)、第三个包(里面放4件)、……、第k个包(里面放2^k件)。(如果放第k+1个包都会超过s[i]，所以最多放在k个包)用公式来表示就是：\displaystyle\sum_{t=1}^k2^t \le s[i] < \displaystyle\sum_{t=1}^{k+1}2^t，我们再补一个常数C，使得\displaystyle\sum_{t=1}^k2^t + C = s[i]，显然C < 2^{k+1}。而0\sim 2^{k+1}-1(即s[i]前面的所有数)可以使用个别组挎包完成。因此我们可以完全拼出0\sim s[i]。
总的来说，对于s[i]个物品，我们可以把他拿掉打2进制个数容量包，如果还有剩下的就另开一包。最多分拆成\lceil logs[i]\rceil个物品。挑选时做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;//2机制个数容量的包
w[cnt] = b * k;
s -= k;
k *= 2;
}
if(s)//最后如果s大于0，说明还有剩下的。
{
cnt++;
v[cnt] = a * s;
w[cnt] = b * s;
}
n = cnt;//01背包大小
最后再做一个01挎包即可。
分组背包问题 有N组物品和一个容量是V的挎包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的容积是v_{ij}，价值是w_{ij}，其中i是组号，j 是组内编号。
求解将什么物品放入挎包，可使物品总容积不超过挎包容量，且总价值最大。
分组背包问题给每种物品分了组，有点像降低限制的多重背包问题。多重背包问题是考虑第i个物品选几个，分组背包问题是考虑第i组物品选那个。因此我们有递推关系：
V[i][j] = max \begin{cases} V[i-1][j],j< w_i \\ V[i-1][j-v[i][k]]+w[i][k],v[i][k]\le j\\ \end{cases}\\
v[i][k]表示第i组，第k个物品。
int v[N][N], w[N][N],f[N],s[N];
for(int i =1; i <=n ; i++)
for(int j = m; j >= 0;j--)
for(int k = 0; k <=s[i];k++)
if(v[i][k] <= j)
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
这里直接使用了聚类优化。
由于我们的地推关系式V[i][j] = max(V[i-1][j],V[i-1][j-v[i][k]]+w[i][k]是由第i-1层得到的，因此我们循环m时须要从大到小循环(这一点和01挎包优化一样)，这样就能保证用到的是i-1层。
这些就是常规的背包问题啦~
