背包问题（完全背包）
1.矩阵链乘法
2.投资组合问题
3.完全背包问题
4.01背包问题
5.最长公共子序列
一个背包，可以放入n种物品，物品j的重量和价值分别为 ，如果背包的最大重量限制是b，怎么样选择放入背包的物品以使得背包的总价值最大？
组合优化问题，设 表示装入背包的第j个物品的数量，解可以表示为 。那么目标函数和约束条件是：
如果组合优化问题的目标函数和约束条件都是线性函数，称为线性规划。如果线性规划问题的变量 都是非负整数，则称为整数规划问题。背包问题就是整数规划问题。限制所有的 时称为0-1背包
子问题的界定（就是靠什么来划分子问题）：由参数k和y界定
k：考虑对物品1,2,3,...,k的选择。
y：表示背包总重
子问题计算顺序：k=1,2,...,k，对给定的k，y=1,2,...,b
：装前k个物品，重量不超过y时的背包最大值。
包含两种情况：不装第k种物品或至少装一件第k种物品。
对 的解释：装一件第k种物品后，最优的解法仍然是在前k个物品进行选择，仍有可能再选入1件第k种物品。
对边界条件:
：即只用第一种物品背包重量限制为y的最大价值，为了保证背包不超重，第一种物品至多能装 个，因为背包价值为
有些 那么通过设置为负无穷，在选择过程中抛弃掉为负的情况。
标记函数：用来追踪解
按照递推公式：以k=2为例子，简单演算如下：
依次类推，可得备忘录表：
标记函数的备忘录：
物品受限背包 ：第i种物品最多用 个
0-1背包问题 ：
多背包 ：m个背包，背包 装入最大重量 在满足所有背包重量约束下使物品价值最大。
二维背包 ：每件物品重量 和体积 ，背包总重不超过b，体积不超过V，使得物品价值最大。
此问题是完全背包问题，即 一个物品可重复出现。
