当前在线人数15403
首页 - 分类讨论区 - 学术学科 - 金融工程版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
银行quant算法题求各位大神帮忙 (转载)
[版面:金融工程][首篇作者:Sarharast] , 2018年08月28日23:21:11 ,2440次阅读,14次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
Sarharast
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: Sarharast (LT), 信区: Quant
标  题: 银行quant算法题求各位大神帮忙 (转载)
发信站: BBS 未名空间站 (Tue Aug 28 23:21:11 2018, 美东)

【 以下文字转载自 JobHunting 讨论区 】
发信人: Sarharast (LT), 信区: JobHunting
标  题: 银行quant算法题求各位大神帮忙
发信站: BBS 未名空间站 (Tue Aug 28 23:19:31 2018, 美东)

online submission 最后一道了 有点像knapsack problem

Minimize Cost of Fruits
There are three types of fruits providing energy 2, 3, 5 respectively, with
amounts given by cnt1, cnt2, cnt3, and the cost of fruits given by cost1,
cost2, and cost3 respectively. Given an energy level S, return the minimum
cost of the fruits that
will give energy S or greater. If no such combination is possible, return -1

def minCost(S, cnt1, cnt2, cnt3, cost1, cost2, cost3):
    pass
--
※ 来源:·iOS 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 76.]

 
littlechong
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: littlechong (一只小虫), 信区: Quant
标  题: Re: 银行quant算法题求各位大神帮忙 (转载)
发信站: BBS 未名空间站 (Thu Aug 30 02:54:49 2018, 美东)

我认为这题不属于背包问题(knapsack problem)。背包问题最重要的特征是限重,而
这道题,水果的数量和重量都没有限制。

这题就是道小学算术题。从已知条件,对于每种水果,不难算得单个水果的价格以及一
个单位energy的价格(energy单价)。只要比较各种水果的energy单价,选出最小值者
,然后买对应这个最小值的那种水果一直买至所含总energy大于等于S,再数出水果个
数及计算cost即可。

【 在 Sarharast (LT) 的大作中提到: 】
: 发信人: Sarharast (LT), 信区: JobHunting
: 标  题: 银行quant算法题求各位大神帮忙
: 发信站: BBS 未名空间站 (Tue Aug 28 23:19:31 2018, 美东)
: online submission 最后一道了 有点像knapsack problem
: Minimize Cost of Fruits
: There are three types of fruits providing energy 2, 3, 5 respectively,
with
: amounts given by cnt1, cnt2, cnt3, and the cost of fruits given by cost1,
: cost2, and cost3 respectively. Given an energy level S, return the minimum
: cost of the fruits that
: will give energy S or greater. If no such combination is possible, return
-1
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 202.]

 
feifeihouzi
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: feifeihouzi (), 信区: Quant
标  题: Re: 银行quant算法题求各位大神帮忙 (转载)
发信站: BBS 未名空间站 (Fri May 17 17:14:35 2019, 美东)

反例:需要100能量,两个水果,分别是99能量99块钱,和1能量2块钱,按照您的算法
需要花198,其实101就够了

不妨试试f(能量,花费)


【 在 littlechong (一只小虫) 的大作中提到: 】
: 我认为这题不属于背包问题(knapsack problem)。背包问题最重要的特征是限重,而
: 这道题,水果的数量和重量都没有限制。
: 这题就是道小学算术题。从已知条件,对于每种水果,不难算得单个水果的价格以及一
: 个单位energy的价格(energy单价)。只要比较各种水果的energy单价,选出最小值者
: ,然后买对应这个最小值的那种水果一直买至所含总energy大于等于S,再数出水果个
: 数及计算cost即可。
: with
: -1



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 64.]

 
littlechong
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: littlechong (一只小虫), 信区: Quant
标  题: Re: 银行quant算法题求各位大神帮忙 (转载)
发信站: BBS 未名空间站 (Sat May 18 02:22:09 2019, 美东)

原题目第一句话:“There are three types of fruits providing energy 2, 3, 5
respectively......”

因此,你举的例子说两个水果,一个能量99,一个能量1,这个意思是与题意不符的,
甚至属于篡改题目。

你可以举一个符合题意的例子说明你的观点吗?

另外,f(能量,花费)只是一种算法统称,你能具体描述一下你的计算方法吗?

【 在 feifeihouzi () 的大作中提到: 】
: 反例:需要100能量,两个水果,分别是99能量99块钱,和1能量2块钱,按照您的算法
: 需要花198,其实101就够了
: 不妨试试f(能量,花费)



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 47.]

 
lavinder
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: lavinder (lavinder), 信区: Quant
标  题: Re: 银行quant算法题求各位大神帮忙 (转载)
发信站: BBS 未名空间站 (Sat May 18 08:51:39 2019, 美东)

大哥你的抽象思维能力堪忧啊

【 在 littlechong (一只小虫) 的大作中提到: 】
: 原题目第一句话:“There are three types of fruits providing energy 2, 3, 5
: respectively......”
: 因此,你举的例子说两个水果,一个能量99,一个能量1,这个意思是与题意不符的,
: 甚至属于篡改题目。
: 你可以举一个符合题意的例子说明你的观点吗?
: 另外,f(能量,花费)只是一种算法统称,你能具体描述一下你的计算方法吗?




--
☆ 发自 iPhone 买买提 1.24.07
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 162.]

 
littlechong
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: littlechong (一只小虫), 信区: Quant
标  题: Re: 银行quant算法题求各位大神帮忙 (转载)
发信站: BBS 未名空间站 (Sat May 18 11:50:05 2019, 美东)

如果ta的观点是对的,为何不能举符合题意的例子?题目规定了3种水果能量分别是2,3
,5,为何要去举能量99的例子?就用题目规定的能量数难道不能支持ta的观点?如果是
这样,ta还在这道题下扯啥呢?

扯淡没有意义,你就回答我在4楼提出的两个疑问就好了。自己不(能)说出个所以然
,只能人云亦云,却说提出疑问的人是能力堪忧。你这种忽悠跟赵本山有一拼。

【 在 lavinder (lavinder) 的大作中提到: 】
: 大哥你的抽象思维能力堪忧啊



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 52.]

 
xiayula
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 7 ]

发信人: xiayula (flow), 信区: Quant
标  题: Re: 银行quant算法题求各位大神帮忙 (转载)
发信站: BBS 未名空间站 (Sat May 18 12:31:08 2019, 美东)

首先formulate i as an mathematical optimization problem.

min(A*cost1+B*cost2+C*cost3)
  subject to:
      2A+3B+5C>=S
      A<=cnt1
      B<=cnt2
      C<=cnt3
      A,B,C>=0

a (integer) linear programming problem, attain minimum at one of the
vertices (use integer part, so search a little bit?)
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
feifeihouzi
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 8 ]

发信人: feifeihouzi (), 信区: Quant
标  题: Re: 银行quant算法题求各位大神帮忙 (转载)
发信站: BBS 未名空间站 (Mon May 20 12:17:02 2019, 美东)

哦哈哈能量235吗,如果cost分别是3,100,5,能量目标是6,你的算法就不对了哈?

其实面试的时候也是,每当candidate给出一个错误的解法,我都得举一个反例,所以
已经习得了快速举反例的能力: )

至于f(energy, cost)的话,可以用f(energy, cost - cost_fruit[i])来递推,最后可
以看目标能量的最小花费

其实另一种方法是正着推,宽度优先搜索即可,但是空间上比较浪费

不管怎样,贪心是不对滴 (no pun intended)

【 在 littlechong (一只小虫) 的大作中提到: 】
: 如果ta的观点是对的,为何不能举符合题意的例子?题目规定了3种水果能量分别是2
,3
: ,5,为何要去举能量99的例子?就用题目规定的能量数难道不能支持ta的观点?如果是
: 这样,ta还在这道题下扯啥呢?
: 扯淡没有意义,你就回答我在4楼提出的两个疑问就好了。自己不(能)说出个所以然
: ,只能人云亦云,却说提出疑问的人是能力堪忧。你这种忽悠跟赵本山有一拼。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 64.]

 
feifeihouzi
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 9 ]

发信人: feifeihouzi (), 信区: Quant
标  题: Re: 银行quant算法题求各位大神帮忙 (转载)
发信站: BBS 未名空间站 (Mon May 20 12:18:35 2019, 美东)

哈哈,既然人家要求了,我已经给出了235的反例,举一反三!


【 在 lavinder (lavinder) 的大作中提到: 】
: 大哥你的抽象思维能力堪忧啊



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 64.]

 
littlechong
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 10 ]

发信人: littlechong (一只小虫), 信区: Quant
标  题: Re: 银行quant算法题求各位大神帮忙 (转载)
发信站: BBS 未名空间站 (Tue May 21 11:05:25 2019, 美东)

我同意7楼xiayula提到的这题属于“linear programming problem”(中文有人译为“
线性规划”)。这种问题有专门的应用软件可用于计算最终结果,“OpenSolver”就是
其中一种。在软件中输入各种决策变量和约束条件,再按个按钮就可以得到答案。

对于决策变量在10个或者以上的题目,使用“线性规划”应用软件是必须的,因为其他
的图表或者算术方法是难以解决的。然而,现在这道题,决策变量只有3个并且其他要
考虑的只有能量数和价格(相当于i=1,2,3;j=1,2),因此我认为算术手工方法可
以解决,不需要作冗余的搜索,也不需要用计算机应用软件计算。

不过,我在2楼的解法,在以下情况下是有bug的,需要修理这些bug。设C2,C3,C5为
三种水果的能量单价:
情况1:C3为能量单价最低者 & 3*C3>2*C2 & S除以3得到的值有小数点部分(非整数)
情况2:C5为能量单价最低者 & 5*C5>2*C2(or 5*C5>3*C3) & S除以5得到的值有小数点
部分(非整数)

以上bug的成因就是小数点部分的能量值以能量单价最小的1个果去抵消在价格上不是最
便宜的,因此:
对于情况1,需要再比较确定小数点部分的能量值是否以n个能量2的果抵消更便宜。(
0<小数点部分的能量值<3,n为小于等于2的正整数)。
对于情况2,需要再比较确定小数点部分的能量值是否以n个能量2 的果or(and) n个
能量3的果抵消更便宜。( 0<小数点部分的能量值<5,n为小于等于3的正整数)。

【 在 feifeihouzi () 的大作中提到: 】
: 哦哈哈能量235吗,如果cost分别是3,100,5,能量目标是6,你的算法就不对了哈?
: 其实面试的时候也是,每当candidate给出一个错误的解法,我都得举一个反例,所以
: 已经习得了快速举反例的能力: )
: 至于f(energy, cost)的话,可以用f(energy, cost - cost_fruit[i])来递推,最后可
: 以看目标能量的最小花费
: 其实另一种方法是正着推,宽度优先搜索即可,但是空间上比较浪费
: 不管怎样,贪心是不对滴 (no pun intended)
: ,3



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 52.]

 
feifeihouzi
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 11 ]

发信人: feifeihouzi (), 信区: Quant
标  题: Re: 银行quant算法题求各位大神帮忙 (转载)
发信站: BBS 未名空间站 (Tue May 21 12:50:40 2019, 美东)

小虫,您的这个新解法,多于这道题而言,只要corner case讨论得足够详细,是可行
的,但是显然比较hacky

对于这类算法题,解法的一般性是大部分出题者所希望的,也是做题者应该追求的,对
于3种水果给出了补丁,那么4种水果、1000种水果又怎么办?时间、空间复杂度又是多
少?只能用软件吗?

而且面试之中难道也要说“用软件”吗?简单情况用hack,复杂情况用软件,我认为这
不算真正弄懂了这个问题。

对于一般性的动态规划解法,时间复杂度是O(energy * num_fruit),f(energy) = f
(energy - energy[i]) + cost[i]; answer = min(f[energy], f[energy + 1], ... f
[energy + max(energy[i]) - 1]),其中f[x]表示达到x能量的最小花费

您看,这个算法可以用数学公式表示,对于计算量也有估计,起码我个人更喜欢这类算
法,在面试之中也希望面试者给出这样的算法。

我知道您可能会说,可是这道题只有三种水果呀,你说那么多n种水果的干嘛?其实对
于三种水果的简单情况,时间复杂度是O(energy^2)的穷举既可,简单易懂,见https:/
/www.hackerearth.com/practice/basic-programming/implementation/basics-of-
implementation/practice-problems/algorithm/energetic-fruits-1ddb5ca3/
editorial/

最后还是希望大家多学算法,贪心、DFS、BFS、动规,多接触数据结构。遇到问题多发
散,举一反三


【 在 littlechong (一只小虫) 的大作中提到: 】
: 我同意7楼xiayula提到的这题属于“linear programming problem”(中文有人译为“
: 线性规划”)。这种问题有专门的应用软件可用于计算最终结果,“OpenSolver”就是
: 其中一种。在软件中输入各种决策变量和约束条件,再按个按钮就可以得到答案。
: 对于决策变量在10个或者以上的题目,使用“线性规划”应用软件是必须的,因为其他
: 的图表或者算术方法是难以解决的。然而,现在这道题,决策变量只有3个并且其他要
: 考虑的只有能量数和价格(相当于i=1,2,3;j=1,2),因此我认为算术手工方法可
: 以解决,不需要作冗余的搜索,也不需要用计算机应用软件计算。
: 不过,我在2楼的解法,在以下情况下是有bug的,需要修理这些bug。设C2,C3,C5为
: 三种水果的能量单价:
: 情况1:C3为能量单价最低者 & 3*C3>2*C2 & S除以3得到的值有小数点部分(非整数)
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 64.]

 
helpme
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 12 ]

发信人: helpme (名虚胖字满肥), 信区: Quant
标  题: Re: 银行quant算法题求各位大神帮忙 (转载)
发信站: BBS 未名空间站 (Mon Jun 10 13:30:05 2019, 美东)

ZAN!


【 在 feifeihouzi () 的大作中提到: 】
: 小虫,您的这个新解法,多于这道题而言,只要corner case讨论得足够详细,是可行
: 的,但是显然比较hacky
: 对于这类算法题,解法的一般性是大部分出题者所希望的,也是做题者应该追求的,对
: 于3种水果给出了补丁,那么4种水果、1000种水果又怎么办?时间、空间复杂度又是多
: 少?只能用软件吗?
: 而且面试之中难道也要说“用软件”吗?简单情况用hack,复杂情况用软件,我认为这
: 不算真正弄懂了这个问题。
: 对于一般性的动态规划解法,时间复杂度是O(energy * num_fruit),f(energy) =
f
: (energy - energy[i]) + cost[i]; answer = min(f[energy], f[energy + 1], ...
f
: [energy + max(energy[i]) - 1]),其中f[x]表示达到x能量的最小花费
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 63.]

[分页:1 ]
[快速返回] [ 进入金融工程讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996