网易笔试题目之一

尛蟲蟲

原题就不赘述了，抽象起来，是这样的：
x，y，z均为非负整数，且有：
x+3y+2z<=200
3x+y+4z<=180
求x,y,z各取多少时，可使得25x+20y+60z取得最大值？
我还没解答出来，稍后附解答过程。

忘记哪，翻出来的了~
应该是楼下村姑的……但是我真的忘记了
就把这个题存TXT里了……

[ 本帖最后由 尛蟲蟲 于 2009-2-9 14:07 编辑 ]

mengweidsg

还是2920，X=0时。。

[ 本帖最后由 mengweidsg 于 2008-10-14 12:23 编辑 ]

村姑

  鄙视斑竹

你转我博客里的东西不提供原地址～！

村姑

我没算出来，笔试时只是把原题（游戏里常见的设置）抽象成这样的了。

后来用excel拉出来答案了。哈哈，还是工具好用。

不过也说明这一块，我的数学能力还需要提高啊

nie

我认为当y=0  z=210  x=-220   时，值为最大     不知对不对

云层

=.=如果是我直接写个c语言的代码来算了。。

村姑

笔试是纸笔…… 当场，限时。

BS-Phoenix

这个考逻辑还是数学? 达人解释一下?

claymore_clare

这个不是很简单的高中数学吗？画个图形就有答案了

gseraph

不难啊，首先非负整数，所以可以得到x<=60,y<=66,z<=45.
因为25x+20y+60z，所以z取最大，所以最大为60*45=2700。此时x和y取0.

gseraph

如果改成30x+35y+60z要最大值就要复杂点了。

lukacrusade

恶补完以前的数学和运筹学知识后算出来了（不过还应该可以用正统数学计算出来吧）~~~

当X=0，Y=44 Z=34时候，MAX为2920

另外，楼上的老兄，你似乎中招了，这种题目貌似最容易得到你这种答案的。

版主快点搞个解法看看，验证下顺便学习~~

[ 本帖最后由 lukacrusade 于 2009-2-6 21:32 编辑 ]

sgbtmy

小弟我算出来也是2920，和楼上一样，当X=0,Y=44,Z=34时。
具体思路如下：
25x+20y+60z=4（5x+4Y+15z）要取最大值可以判断要主要看z的值。
在假定值为K，那么z减小1，y要增加15/4或是x增加3来补回。
由上面不等式,z<=45
且由约束条件2式中，z的值每减小1，就会有两种情况，x增加1，y增加1，或是x增加0，y增加4。
由此可以看出，当x=0时，会有最k=4（5x+4Y+15z）<4（5x+(4Y+4)+15(z-1)）
当然不是z=0时，y=180最大，因为还有不等式1的条件约束，此时求交点，z=34，y=44，此时当z-1时y的增加数就不是4了，而是2/3，所以当x=0,y=44,z=34时有最大值。

lukacrusade

。。。查实我不知道你这么做行不行，如果真的有这样简便判断的话都是好事。
不过首先你该改一改：
25x+20y+60z=4（5x+4Y+15z）这里有问题，应该是“5”（5x+4Y+“12”z）

另外，总觉得怪怪的，你说“由约束条件2式中，z的值每减小1，就会有两种情况，x增加1，y增加1，或是x增加0，y增加4”，但是根据约束条件1，z减少1，若你按“整数”来计的话，y只能加0。所以此时，z减少1，x加0，y加4的情况不成立。。。。你的判断是脱离约束1进行的。

接着，最大迷惑的是你在脱离约束1的情况下判断x=0了，再考虑约束1。为什么不是先考虑约束条件1判断后再考虑约束条件2呢？先不说这么做可不可以，但就论述而言就不全面。。。。
而你定了X的死罪后，交点才可以得到。就是说你这种方法关键是X=0的论证是否成立。

呵呵，我的疑惑主要是这里？

[ 本帖最后由 lukacrusade 于 2009-2-9 21:58 编辑 ]

sgbtmy

首先更改25x+20y+60z=4（5x+4Y+15z）这里有问题，应该是“5”（5x+4Y+“12”z），谢谢楼上
我上面的是简单的写上去的，其实我开始分析的时候把X,Y,Z都做了分析的，由于比较长，所以就省略了。打字比较麻烦。
这里看一下，如果去考略约束条件1，Z<=100,而2中是z<=45。明显1的条件是放大了的。所以在考虑Z条件的时候条件2的约束包含条件1的约束的。
另外，如果只看条件1的情况，x+3y+2z<=200，当z减小1的时候，x,y的增加量不管在什么条件下都是会小于下面的增值
“25x+20y+60z=4（5x+4Y+15z）要取最大值可以判断要主要看z的值。
在假定值为K，那么z减小1，y要增加15/4或是x增加3来补回。”
所以只有在z取最大值的时候有最大量，得到10楼的结果
25x+20y+60z，所以z取最大，所以最大为60*45=2700。此时x和y取0。
显然是错误的。（其实这个也是判断过的，只是没有写出来）
那在什么条件下要考虑条件1呢？在取判断Y的值的时候，条件1中Y<=66，而条件2中Y<=180,所以在确定Y的值的时候要去考虑条件1.

那说清上面的问题后，我们就来看争论的焦点。为什么要判断X=0。
先看25x+20y+60z，在假定值为K，那么z减小1，y要增加15/4或是x增加3来补回。
这个分析没有问题吧？
怎么能是k`>k呢？
我们先来看条件1，z减少1，y增加2/3,或是x增加2，这么看都k`都要小于K。在Z=45，K=2700.
再来条件2，且由约束条件2式中，z的值每减小1，就会有两种情况，x增加1，y增加1，或是x增加0，y增加4。在第二种情况的条件下才有可能使k`>k。
所以判断，只有在x=0的时候有最大值。这样对不？
在一个什么样的情况下，条件2中的情况在条件1中也可以使用呢？
3y+2z<=200
y+4z<=180
求值，画图就知道了，在0<=y<=44,0<=z<=34这个区域内这两个不等式是恒成立的，所以最大值就在这里面。这样解释因该可以成立了吧。

skykklove

我把这个翻到前面去喔

yetties2005

这个楼主是ＢＴ

bang2rui

2920
25x+20y+60z=4（5x+4Y+15z）的，所以X,Y,Z都大才是最大值，其中优先为Z,X,Y
X,Y,Z均为非负数，要让他们为最大值，所以分析可知公式1和公式2可以就看做是等式

到了这里也就是解三元一次不定方程x+3y+2z=200，x+y+4z=180，可以尝试从Y=0依次考虑到Z=0，最后就是解方程，带入

最后答案2920

skykklove

原帖由 yetties2005 于 2009-4-10 02:14 发表
这个楼主是ＢＴ

lukehzg

恩，好好学数学有用~！

[ 本帖最后由 lukehzg 于 2009-5-5 15:44 编辑 ]