背包问题 一
01背包：
- 一般的题目描述是：有N 件物品和一个容量为V 的背包。放入第i 件物品耗费的费用是Ci，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
- 用子问题定义状态：即 dp[i][v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值。
//dp[N][V]；注意：输入的起始地址为1；初始化dp，都为0; for(i=1 ; i<=N ; i++) for(j= c[i] ; j<=V; j++)//注意是从小到大； dp[i][j]=max(dp[i-1][j],dp[i-1][j-C[i]]+W[i]); // 则dp[N][V]就是要找的值；
- 以上方法的时间和空间复杂度均为O(V N)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O(V)。
for(i=1 ; i<=N ; i++) for(j= v; j>=c[i]; j--)//注意是从大到小； dp[j]=max(dp[v],dp[v-C[i]]+W[i]); // 则dp[N][V]就是要找的值；
- PS：实际上会有两种情况，一个是恰好装满，dp[0]=0, 其他需要初始化为负无穷；一个只是寻找最优的解决方案，全部初始化为0就行了；
完全背包：
- 这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件??等很多种。
如果仍然按照解01背包时的思路，令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。
- 仍然可以按照每种物品不同的策略写出状态转移方程，像这样
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i] | 0<=k*c[i]<=v}
- 但是可以转化为01背包来解决为题； 初始化时 dp[V] 都为0； 输入从下标一开始；
for(int i=1 ; i<=n ；i++) for(int j=c[i]; j<=V; j++)//注意：从小到大； dp[j]=max(dp[j],dp[j-c[i]]+w[i]); //最后的结果就为;dp[V];
多重背包：
下面进入关键时刻，完全背包：
另一种好想好写的基本方法是转化为01背包求解：把第i种物品换成n[i]件01背包中的物品，则得到了物品数为Σn[i]的01背包问题，直接求解，复杂度仍然是O(V*Σn[i])。
但是我们期望将它转化为01背包问题之后能够像完全背包一样降低复杂度。
仍然考虑二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略——取0..n[i] 件——均能等价于取若干件代换以后的物品。
另外，取超过n[i]件的策略必不能出现。
方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，
按照总的价值来分，如果那个商品的数量为1，就按01，背包，如果是多个，就按完全背包，来解答；
看看例题吧： HDU 2844 HUD 1059