贪心算法是一种启发式(Heuristic)算法, 它的基本思想是在每一步决策时选择局部最优的策略. 贪心算法一般在设计和实现上比较容易, 因此在求解实际问题中应用广泛.编码问题考虑如下的编码问题: 给定字符的集合CCC, 例如C={a,b,c,d,e}C=\{a, b, c, d, e\}C={a,b,c,d,e}. 每个字符α∈C\alpha\in Cα∈C的使用频次为fαf_{\alpha..

原始对偶(Primal-Dual)是一种求解优化问题的思想, 在凸优化和组合优化问题中有重要应用. 本文以线性规划问题为例解释原始对偶算法的设计思路, 进而介绍如何设计基于原始对偶的近似算法(一般用于求解NP-hard问题).互补松弛条件考虑线性规划的原始问题(P)和对偶问题(D)如下:min⁡ cTxs.t. Ax≥bx≥0(P)\begin{aligned}\min\ &a

三维装箱问题的业务场景可以参考电商业务中的纸箱推荐问题. 文中考虑了如下问题.输入 :长宽高为(L,W,H)(L, W, H)(L,W,H)的箱子和nnn个物品, 其长宽高为(li,wi,hi)(l_i, w_i, h_i)(li​,wi​,hi​), i=1,2,…,ni=1,2,\ldots,ni=1,2,…,n. 假设物品是长方体, 长度不可变(没有弹性). 装箱时可以对商品进行90...

对偶单纯形算法教程（附代码）

业务背景网易严选是一家自营电商，每天有数以万计的订单需要拣货、打包和出库。打包的过程就是把订单中的商品用包材进行包裹，常见的打包方式有缠膜、装袋和装箱。袋子和箱子有不同的种类和型号，比如袋子有共挤膜袋、镀铝膜袋、塑料袋等。仓库作业工人需要对商品按订单进行打包。具体来说，主要决策两件事：第一，根据订单的商品选择正确的包材类型。比如服装毛巾等柔软的商品适合用袋子；易碎品、液体和贵重物品适合用纸箱；有些

引言本文介绍了一个经典的商品采购模型(报童问题)及其解法. 该模型通过考虑需求的不确定性来最大化销售利润.注: 本文的主要内容参考Gallego1.1. 报童问题这是一个关于卖报商人采购报纸的问题. 每天早上, 卖报商以批发价0.3元(每份)向报社采购当天的报纸, 然后以零售价1元(每份)进行售卖. 如果报纸在当天没有卖完, 他会把报纸以0.05元(每份)的价格卖给废品回收站.那么卖...