我目前接触到背包分为4类，我将逐类介绍
1求背包能装物品价值的最大值
这类问题的模型是 存在一个 容量（重量方面 不考虑体积）为M的背包 现在有n个物品 他们的质量为M[i] 价值为V[i]，求能装的物品的最大总价值
这个是 一个典型的动态规划的题目 对于容积进行动态规划，定义F[i] 为容积为i下的能容纳的最大总价值
那么如果在多一个物品k的时候存在这样的关系 F[I] = MAX(F[I- M[K]] + V[k],F(I))
这里其实为了节省空间把二维数组压缩到了线性，更直白的可以定义F[I][N] 表示在容积I下 前N个物品能存放的最大总价值
数组压缩到了线性也对程序带了限制 动态式中的 F[I-M[K]]对应着二维F(I-M[K])(K-1) 而 F[I]对应着F[I][K]
所以为了保持等式成立 必须从大端向着小端规划
用我自定义的伪代码表示
for 1：n //物品个数
input（m,V） //输入物品质量和价值
for i=M：m //物品只可能影响不小于自身质量的方案
F[I] = MAX(F[I- M[K]] + V[k],F(I))
案例可以参考我之前的博客acm39开心的小明
2完全最大值背包问题
问题模型是 存在一个容量为M的背包，现在有n个物品 他们的质量为M[i] 价值为V[i]， 每种物品的数量不限，求能装满背包的方案所能有的最大价值 ，如果不能则输出NO
完全背包因为需要考虑最大值的问题，随意可以用到之前的动态分析基本式
但是在实现需要做个改变
for 1：n //物品个数
input（m,V） //输入物品质量和价值
for i=m：M //物品只可能影响不小于自身质量的方案
F[I] = MAX(F[I- M[K]] + V[k],F(I))
要点一
这道题和之前的最大值为存在一个区别就是 动态规划的时候是从高到低和还是从低到高
最大值问题采用从高到低的策略 因为这样可以避免物品重复的问题，添加一个物品他所考虑的情况都是不包含本身的情况
本体采用从低到高是因为物品可以重复，当考虑物品k时 如果添加一个物品k 能获得空间i+m[k]下的最佳方案，那么在考虑空间i+m[k]的时候 方案里可以包含了至少一个物品K
要点二
F[i]数组初始化的时候要赋值一个负值，但是第0位应该赋值为0，这个负值的大小是有测试数据决定的。
至于这样做的原因是要保证数组能够填满，那这是为什么？因为如果我们全部初始为0，那么我们考虑这种情况，
测试数据：
1
1 50
49 1
最后结果是1 这肯定是不对的
我们回到之前动态规划的基础，我们只考虑了要让得到的价值最大，但是我们却没有考虑背包是否被完全装满，
那么我们此时需要考虑装不满是什么情况：留出的空间是小于输入的重量数据最小的数
换句话说 这样的情况在于 我们最后得到的最大情况是基于f（i） 0<i<min（物品重量） 的情况得到
案例可以参考我之前的博文acm311
3求能装满背包的方案数
问题模型是 存在一个容量为M的背包，现在有n个物品 他们的质量为M[i] ，求能恰好装满背包的方案总数
这个是我之前研究完全背包问题的时候看到的，这里做点总结
这个也是一个动态规划的问题，定义一个F[I][n] 表示前n项中能恰好填满空间i的方案数
那么就有如果增加一个物品K
那么F[I][K] = F[I][K-1] M[K] >I
F[I][K-1]+F[I-M[K]][K-1] M[K]<=I
参照定义不难理解
伪代码我就不写了
4求能装满背包的方案数变体
问题模型是 存在一个容量为M的背包，现在有n个物品 他们的质量为M[i] ，物品无限使用 求能恰好装满背包的方案总数
这个针对上一个区别在于物品无限使用 函数定义参照之前
那么F[I][K] = F[I][K-1] M[K] >I
F[I][K-1]+（∑ （F[I - k*j][k-1]）） M[K]<=I
这个只不过需要多考虑一次添加多个同样物品的情况
3和4都能把空间压缩到线性，和问题1，2是一个原理
另外附上背包问题3,4参考的来源http://blog.csdn.net/wumuzi520/article/details/7021210