《数学建模之排序方法》由会员分享，可在线阅读，更多相关《数学建模之排序方法（4页珍藏版）》请在金锄头文库上搜索。
1、 选，还是不选 -关于有限资源选择最大效益问题一、 关于生活中常见的选择问题 生活中时时刻刻会有选择的发生，这些选择，无疑于围绕着两个问题，那就是价值和成本，许多东西并不简简单单可以用一个函数来解决，因为生活中的问题常常不仅有一个变量的发生，而是牵扯到许多的选择，因此，简简单单的函数已无法解决这些问题，所以需要从新建模与寻找方法。二、 关于建模背景和建模目的。 日前，随着改革开放的步骤，科技发展的新风，许多家公司正在引进新机器，由于机器成本较高，公司资金有限，每种只能置办有限的几台。已知每台机器所能够创收的效益，和总共所拥有的资金数，问如何才能尽可能多的获得经济效益。 也许，生活中的问题没有如
2、此死板，但通过建模，却可以对此类问题有很好的理解和更优秀的选择方式，因此，选择此题为建模模型，进行数学探究。三、 采样与假设 为了先行对题目内容有大概了解，更好的明白建模目的。我们可以通过一个样例来说明、 成本 收益总 70 物品1 71 100物品2 69 1物品3 1 2 对于如此一个题目，我们可以直接枚举，直观的看出选择物品2，3是可以获得最大的收益，为3，当然这种简单的样例，是可以直观得出结论的，但是对于复杂的呢。例如：数据说明：第一行两个数：物品总数，资金总量W；第二行N个数,为种物品所用资金Wi第三行N个数,为N种物品收益Vi(1000); 输入样例：4（n) 10(m)wi4 3
3、 5 7vi15 7 20 25输出样例：通过细心地枚举，可以得出此题最优解为35四个数据，相比于三个数据而言，就比较难以找到它的最优解值。因此，我们需要建模，用系统的方法来解决这一问题四、建模与模型分析：方法一：对于此类问题，我们首先可以引用贪心的算法。即，我们可以通过求各个物品的性价比来选择，即选择单位成本内，各物品的价值，通过性价比来排序，从而获得最优解值同样可以通过此样例来看设性价比为ci则四物品性价比为Ci3.75 2.33 4 3.285714根据性价比排序，选择顺序应为3，1，4，2则有限总资金之内可以达到的最大值为35，看来，贪心算法适合于此实例。但有些数据该方法却无法很好解决
4、。例：3 100V w100 9950 5050 50若依旧通过性价比排序的方法则得到的结果为99，实际最优值应为100，因此，贪心算法得到的不一定是最优值。方法二：看来单纯的数学算法无法解决这个问题。因此我们还是要归结于枚举思想，那是否有简单直观，且利于一次解决问题，不会漏的方法呢设fi,j为选到第i个物品，花费为j的最大收益则fn,m为选到第n个物品，花费为m的最大受益，即最终解值对于fi,j的计算，面对的选择有两个，极为选与不选，选，则Fij:=fi-1,j-wi+vi;(这个式子的意思自己多想想就明白了）不选则fi,j:=fi-1,j所以，可以得到dp是fI,j=maxfi-1,j,fi-1,j-Wi+Vi (1=i=n,1=j=m)下图可供参考ji背包的容量0-10背包的容量0-10背包的容量0-10通过上述方法就可以很好的解决选择问题，对于生活实例的处理也可以变得明晰化
