揉饼糊 难题求大神解

知道怎么解了。用dp
存 有x元时的最大收入 依此递归

provhomme 发表于 2019-9-22 10:32
如果没理解错的话，是不是可以直接greedy买最大收益的股票的最大数量，然后买次大收益的股票的最大数量 。 ...

我是这么写的但是应该不对。比如你有10元。A股卖6块，未来卖8块。B股卖5块，未来卖6.5块。那么最佳策略是买2股B而不是买1股A   

HanBurger 发表于 2019-9-24 03:07
今天被面了同一道题，小哥在我做题前提了一句可以买fraction number of stocks...于是觉得这应该是一个简单 ...

额。。。我就是这么挂的。。。当时隐约觉得不是这么简单但是小哥一直反应的很postive加上我又一下想不起来dp应该怎么解。。。

如果没理解错的话，是不是可以直接greedy买最大收益的股票的最大数量，然后买次大收益的股票的最大数量 。。。直到本金用完？

cser017 发表于 2019-9-22 10:38
我是这么写的但是应该不对。比如你有10元。A股卖6块，未来卖8块。B股卖5块，未来卖6.5块。那么最佳策略是 ...

谢谢提醒。那这题是个二维dp，一个维度i是从0到M元的最大收入，另外一个维度j是i时买卖股票的数量。

provhomme 发表于 2019-9-22 12:38
谢谢提醒。那这题是个二维dp，一个维度i是从0到M元的最大收入，另外一个维度j是i时买卖股票的数量。

嗯。另一个维度要存还可以买的数量，因为每个股票有最高限制。赞！～

这是背包问题把

HanBurger 发表于 2019-9-23 07:59
这是背包问题把

真是个多重背包。多年前还做过。。看来太久没练还是有些生疏了。。。
找了个总结贴： https://blog.csdn.net/u013166817/article/details/85449218

cser017 发表于 2019-9-23 08:13
真是个多重背包。多年前还做过。。看来太久没练还是有些生疏了。。。
找了个总结贴： https://blog.csdn ...

楼主应该是太久没面试了生疏了
明天面他家，感觉面经都没看到多少，谢谢楼主分享了

这个感觉确实是多重背包，楼主加油吧