美国华人网FuninUSA_唐人社区_北美华人论坛:找礼品卡,找折扣,找报价,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • 小龙女报警抓母不算啥!朱茵曾说过的话才是惊恐
  • 何洁过生日晒美照 自称为爱奋不顾身付出
  • 原来左撇子的甜馨字这么漂亮,老爸贾乃亮都自叹不如
  • 体验生活?薛之谦被曝KTV撩妹抽烟
  • 章子怡好继母人设崩塌?小苹果一直跟奶奶住
  • 安琥签约诚利风尚迎首秀?亮相Cabbeen时装发布会
  • 大家更爱健康:可口可乐、百事可乐心酸没人喝
  • 秘鲁10年一遇洪灾 男子洪水中开车:这一幕太惊险
  • 海豚猛撞河豚竟为逼出毒素:吸了会兴奋上瘾
  • 汪小菲为老婆儿女做什么了能让大S这样称赞?
  • 在“中性”评级下,Snapchat股价不断攀升
  • 英特尔能够抓住自动驾驶新革命吗?
  • 医疗改革,联合健康将极具吸引力
  • IBM:只有适应才能变得更好
  • AMD将打破这暴风雨前的平静
  • 为什么特朗普交易仍然完好无损?
  • 如果特朗普的医保法案通过,谁会是赢家?
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3014|回复: 5

内推面经 -01背包问题- 唐人社区|北美华人论坛

[复制链接]

19

主题

375

帖子

411

积分

中级会员

Rank: 3Rank: 3

积分
411
QQ
发表于 2016-10-29 03:18:26 | 显示全部楼层 |阅读模式
分享到:
{$content}

唐人社区-北美华人论坛-内推面经版-01背包问题


  JobHunting
标 题: 01背包问题


如果要输出放入了哪些宝石,是不是只能用2D space DP?
--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?

新浪微博官方号:美国华人网FunInUSA 新浪微博官方号:美国省钱快报FunInUSA 微信公众号:玩美生活FunInUSA
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

19

主题

94

帖子

132

积分

注册会员

Rank: 2

积分
132
QQ
发表于 2016-10-29 06:05:04 | 显示全部楼层
JobHunting
标  题: Re: 01背包问题


明白了,那要用两个1D array,一个存最大价值(结果),一个存最后宝石的重量或体积

【 在 Livinghere (Livinghere) 的大作中提到: 】
: 1D也能backtrace出放哪些宝石,总时间复杂度不变。



--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?

20

主题

91

帖子

131

积分

注册会员

Rank: 2

积分
131
QQ
发表于 2016-10-29 06:25:17 | 显示全部楼层
JobHunting
标  题: Re: 01背包问题


1D也能backtrace出放哪些宝石,总时间复杂度不变。
--

24

主题

96

帖子

153

积分

注册会员

Rank: 2

积分
153
QQ
发表于 2016-10-29 06:54:21 | 显示全部楼层
JobHunting
标  题: 01背包问题


如果要输出放入了哪些宝石,是不是只能用2D space DP?
--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?

23

主题

101

帖子

151

积分

注册会员

Rank: 2

积分
151
QQ
发表于 2016-10-29 07:48:12 | 显示全部楼层
JobHunting
标  题: Re: 01背包问题


都是时间和空间的tradeoff
1D space也能搞,每一步遍历所有宝石即可
【 在 coldknight (冷骑士) 的大作中提到: 】
: 如果要输出放入了哪些宝石,是不是只能用2D space DP?



--

23

主题

1213

帖子

2400

积分

金牌会员

Rank: 6Rank: 6

积分
2400
QQ
发表于 2016-11-28 02:23:14 | 显示全部楼层
求沙发
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

美国华人网|唐人社区|什么值得买FunInUSA.net发布的内推面经 -01背包问题- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -01背包问题- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
Sasa.com

Copyright ©2011 FunInUSA.NET All Right Reserved.  Powered by Discuz! X3.0 小黑屋

本站信息均由会员发表,不代表美国华人网FunInUSA|唐人社区的立场,如侵犯了您的权利请发帖投诉  技术支持: 美国华人网FunInUSA|唐人社区

安全联盟认证 安全联盟认证

快速回复 返回顶部 返回列表