体验编程之美 饮料供应问题

动态编程，贪婪算法，实际问题的建模过程

现实问题描述

  公司水房提供很多种类饮料，已经统计获得大家对每种饮料的满意程度；STC负责给公司提供饮料，每天的总容量为V，每种饮料的单个容量都是2的方幂，比如王老吉，都是2的三次方为8升的；STC的存货也是有限的，这会是每种饮料的购买量上限。统计数据中使用饮料名字，容量，数量，满意度来描述一中饮料，问如何保证最大的满意度啊。

问题建模

  我刚看到这道题目的时候，其实是很困惑的，完全不知道该如何下手。因为之前刷leetocde算法题目时，每个题目是使用编程域的语言进行描述的，比如：复制一个具有随机指针的链表。而这道题却是一个完全现实问题域描述，这样我们就需要进行建模，将这个实际问题转换为之前比较常见的算法问题。

  假设ST提供n种饮料，用(Si,Vi,Ci,Hi,Bi) (对应饮料的名字，容量，可能的最大数量，满意度，实际购买量)来标示第i中饮料，其中可能的最大数量指如果仅买这种饮料的可能最大数量，比如对第i种饮料，Ci=V/Vi;

  基于现实域的描述，我们有以下两个公式：

• 饮料的总数量 V= (V0B0)+(V1B1)+……….(Vn*Bn); A

• 总满意度为 H=(H0B0)+(H1B1)+………(Hn*Bn); B

  那么题目的要求就是，在满足饮料总数量为V的基础上，求解最大的总满意度。

动态编程

 对于最优解问题，首先考虑到动态编程啦！用Opt(V’,i)来标示从第i,i+1,……n-1,n种饮料中，计算出总量为V’的方案中满意度之和的最大值。

 然后我们思考一下最优子结构的推到公式啊。Opt(V’,n)=max{kHi+Opt(V’-Vik,i-1)} (k=0,1,2,Ci),简单描述一下就是先将V‘分成两份，一份是Si饮料容量，大小为KVi；另外一份是其他的饮料的容量，大小为V’-Vik,其中k表示这种饮料的数量。然后取不同的k值，范围为0到Ci,求最大的满意度。

 我们来列出动态编程的初始化条件：

• Opt(0,0)=0

• Opt(x,n)=-INF

对动态编程的优化

  动态编程算法的一个变形是备忘录法，备忘录法也是用一个表格来保存每个子问题的答案，并通过记忆化搜索来避免计算一些不可能到达的状态，简单来说，就是避免重复计算子问题，第一次遇到子问题的时候进行计算，然后保存结果，之后再次遇到时，直接取出结果使用。
  动态编程和备忘录法的区别就是：动态编程是自下到上，而备忘录法是自顶向下的，而且备忘录法可以进行多次查询，花费了存储空间，来提高整体查询效率。

贪婪算法

  一般来说，如果你发现了最优子结构和重复子问题，就可以使用动态编程了，但是如果你发现了下边这条更加特殊的性质，你就可以使用贪婪算法.
  这个特性就是贪心选择性质：我们可以通过局部最优（贪心）选择来构造全局最优，换句话说，当进行选择时，我们直接做出在当前问题中看来最优的选择，而不必考虑子问题的解，这就是贪婪和动态编程的区别，动态编程的每一步选择通常依赖于子问题的解，而贪婪不需要。
  回到饮料供应问题，可以设想，将饮料按照满意度大小进行排序，优先最大量供应满意度最大的饮料是否就能得出这个问题的最优解呢？答案是肯定的，我们可以对这性质进行证明。
  这篇文章只是分析了饮料供应问题的算法原理，并没有给出具体代码，大家可以自己动手编写一下啊，理论和实践并行啊。