题目
题目来自《编程之美》：在微软亚洲研究院上班，大家早上来的第一件事是干啥呢？查看邮件？No，是去水房拿饮料：酸奶，豆浆，绿茶、王老吉、咖啡、可口可乐……（当然，还是有很多同事把拿饮料当做第二件事）。
管理水房的阿姨们每天都会准备很多的饮料给大家，为了提高服务质量，她们会统计大家对每种饮料的满意度。一段时间后，阿姨们已经有了大批的数据。某天早上，当实习生小飞第一个冲进水房并一次拿了五瓶酸奶、四瓶王老吉、三瓶鲜橙多时，阿姨们逮住了他，要他帮忙。
从阿姨们统计的数据中，小飞可以知道大家对每一种饮料的满意度。阿姨们还告诉小飞，STC（Smart Tea Corp.）负责给研究院供应饮料，每天总量为V。STC很神奇，他们提供的每种饮料之单个容量都是2的方幂，比如王老吉，都是23=8升的，可乐都是25=32升的。当然STC的存货也是有限的，这会是每种饮料购买量的上限。统计数据中用饮料名字、容量、数量、满意度描述每一种饮料。
分析：此处构造的最优子结构和实现的代码不同于《编程之美》，采用动态规划自底向上的方法解决该问题。
1、数学建模
假设STC供提供n中饮料（n=1,2,...n），对应饮料的参数如下
要求的问题描述如下：
饮料总量为
在这个前提下，求解使总满意度最大，即
对于最优化问题，可以考虑是否能用动态规划求解。同时，该问题很类似于01背包问题，即在总量一定的前提下，使总价值（此处为满意度）最大，所以可以借鉴01背包问题的思想来解决该问题。
2、动态规划求解
2.1描述最优子结构
用f(i)来表示选取饮料i时的最大满意度。假设f(i-1)是选取饮料i-1时的最大满意度，那么
f(i)=max{f(i-1)+k*H[i]} (v[i-1]*k<=v',v'为f(i-1)时的剩余重量)
其中k=0,1,...,c[i]。
可以证明f(i)为饮料i时的最大满意度，假设如果还有比f(i-1)还大的满意度，则可替换，但是这个假设与f(i-1)是选取饮料i-1时的最大满意度矛盾。
由此确定的最优子结构为
2.2递归定义最优解的值
当i=1时，f(1)=max{k*H[i]}
当i>1时，f(i)=max{f(i-1)+k*H[i]} (v[i-1]*k<=v',v'为f(i-1)时的剩余重量)
其中k=0,1,...,c[i]。
终止条件：f(0)=0(没有饮料时，满意度为0）
2.3按自底向上方式计算最优解的值
用数组f记录满意度，f[n]为最优满意度，初始值为f[0]=0。数组remainV记录当前剩余总重量，初始值为 remainV[0]=V。数组resultK记录对应饮料选择的最终数目，用于构造最优解，初始值为
resultK[0]=0。
伪代码如下
- <span style="font-size:18px;">/*
- n=1,2,...n 饮料名称
- V饮料总量上限
- */
- f(n,V,C,H){
- //初始化
- f[0]=0; //数组f记录满意度，f[n]为最优满意度
- remainV[0]=V; //数组remainV记录当前剩余总重量
- resultK[0]=0; //数组resultK记录对应饮料选择的最终数目，用于构造最优解
- for(int i=1;i<=n;i++){ //饮料名称
- currentf=f[i-1];
- for(int k=0;k<=c[i];k++){
- //剩余重量判断
- tempV=k*v[i];
- if(tempV>current[i-1])
- break;
- tempf=f[i-1]+k*H[i];
- if(temp>=currentf){
- curretnf=temp;
- resultK[i]=k;
- }//end if
- else
- resultK[i]=result[i-1];
- }//end for
- //记录剩余重量
- currentV[i]=current[i-1]-resultK[i]*v[i];
- }//end for
- //返回最优满意度
- return f[n];
- }//end f</span>
2.4由计算出的结果构造一个最优解
- <span style="font-size:18px;">//根据resultK构造最优解
- for(int i=1;i<=n;i++){
- System.out.println("饮料"+i+选取的数目为"+resultK[i]);
- }//end for</span>
算法时间复杂度：
子问题个数为饮料种类数目n,每个子问题的选择数目为该种饮料的最大上限数目c[i],所以时间复杂度为O(n*max{c[i]})，算法中用3个长度为n+1的数组保存值，故空间复杂度为O(n)