数学建模之排序方法

《数学建模之排序方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、选，还是不选----------------关于有限资源选择最大效益问题一、关于生活中常见的选择问题生活中时时刻刻会有选择的发生，这些选择，无疑于围绕着两个问题，那就是价值和成本，许多东西并不简简单单可以用一个函数来解决，因为生活中的问题常常不仅有一个变量的发生，而是牵扯到许多的选择，因此，简简单单的函数已无法解决这些问题，所以需要从新建模与寻找方法。二、关于建模背景和建模目的。日前，随着改革开放的步骤，科技发展的新风，许多家公司正在引进新机器，由于机器成本较高，公司资金有限，每种只能置办有限的几台。已知每台机器所能够创收的效益，

2、和总共所拥有的资金数，问如何才能尽可能多的获得经济效益。也许，生活中的问题没有如此死板，但通过建模，却可以对此类问题有很好的理解和更优秀的选择方式，因此，选择此题为建模模型，进行数学探究。三、采样与假设为了先行对题目内容有大概了解，更好的明白建模目的。我们可以通过一个样例来说明、成本收益总70物品171100物品2691物品312对于如此一个题目，我们可以直接枚举，直观的看出选择物品2，3是可以获得最大的收益，为3，当然这种简单的样例，是可以直观得出结论的，但是对于复杂的呢。例如：数据说明：第一行两个数：物品总数Ｎ，资金总量W；第

3、二行N个数,为Ｎ种物品所用资金Wi第三行N个数,为N种物品收益Vi(<1000);输入样例：4（n)10(m)w[i]4357v[i]1572025输出样例：通过细心地枚举，可以得出此题最优解为35四个数据，相比于三个数据而言，就比较难以找到它的最优解值。因此，我们需要建模，用系统的方法来解决这一问题四、建模与模型分析：方法一：对于此类问题，我们首先可以引用贪心的算法。即，我们可以通过求各个物品的性价比来选择，即选择单位成本内，各物品的价值，通过性价比来排序，从而获得最优解值同样可以通过此样例来看设性价比为c[i]则四物品性价比为

4、C[i]3.752.3343.285714根据性价比排序，选择顺序应为3，1，4，2则有限总资金之内可以达到的最大值为35，看来，贪心算法适合于此实例。但有些数据该方法却无法很好解决。例：3100Vw1009950505050若依旧通过性价比排序的方法则得到的结果为99，实际最优值应为100，因此，贪心算法得到的不一定是最优值。方法二：看来单纯的数学算法无法解决这个问题。因此我们还是要归结于枚举思想，那是否有简单直观，且利于一次解决问题，不会漏的方法呢设f[i,j]为选到第i个物品，花费为j的最大收益则f[n,m]为选到第n个物品

5、，花费为m的最大受益，即最终解值对于f[i,j]的计算，面对的选择有两个，极为选与不选，选，则F[ij]:=f[i-1,j-w[i]]+v[i];(这个式子的意思自己多想想就明白了）不选则f[i,j]:=f[i-1,j]所以，可以得到dp是f[I,j]=max{f[i-1,j],f[i-1,j-W[i]]+V[i]}(1<=i<=n,1<=j<=m)下图可供参考ji背包的容量0--10背包的容量0--10背包的容量0--10通过上述方法就可以很好的解决选择问题，对于生活实例的处理也可以变得明晰化