运筹学中有四个典型问题：切割余料问题（cutting stock problem），集合划分问题（set partitioning problem），装箱问题（bin packing problem）和背包问题（knapsack problem），它们的数学形式很相似，并且联系也十分紧密，因此我经常弄混淆。今天查了Wiki百科，才最终明白这四个问题的起源，数学形式和求解方法。现在把我的心得共享出来，希望对大家会有帮助：

背包问题可以描述为：给定一组物品，每种物品都有相应的重量w和价值p，在限定总重量W内，我们如何选择，才能使得得到的总价值最高。它的数学形式如下：

http://s13/middle/62f9f07b4b1febd31e93c&690

背包问题按照决策变量x的取值范围分为0-1背包问题、有界背包问题和无界背包问题，其中最后一个最容易求解。背包问题属于NP完全问题，但是目前它可以通过伪多项式算法（动态规划）求解。

背包问题是装箱问题的一种特殊形式，它只考虑一个包（箱）的情况，当系统内有多个包（箱）时，需要考虑如何选择装载方式使得所用包（箱）的总和最少（因为是相同的箱，因此目标函数的系数都相同）。这样的问题就叫做装箱问题。

装箱问题通常可以用best fit decreasing 和 first fit decreasing 两种贪恋算法求解，但是都不能保证解的最优性。装箱问题另外一个子问题叫做集合划分问题（set partitioning problem）它是指如何将一组整数元素划分为两个（或多个）集合，使得每个集合中所有元素之和相等（差异最小化）。

切割余料问题是指有一批长度为L的原料，而需求却是各种长度为lj的用料，对应的需求量是qj。如何进行切割，使得在满足需求的前提下浪费的原料最少。它通常分为主问题和子问题，主问题是指如何选择切割方案使得余料最少，由于切割方案太多，通常主问题只考虑部分的切割方案，当需要的时候由子问题产生一个新的切割方案（主问题的一列），这就是列生成的方法。切割余料问题的子问题是一个背包问题，产品的定价通常采用主问题中资源的影子价格。主问题的数学形式如下：

http://s15/middle/62f9f07b4b1fec1caa89e&690