【每日一题】8月19日题目精讲-装货物

题号 NC200532
名称 装货物
来源 牛客练习赛57
戳我进入往期每日一题汇总贴~
往期每日一题二期题单

图片说明

如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情

题解

可以暴搜,搜的时候维护当前每个箱子的剩余空间,如果当前这个物品能放进之前的某个已经放了物品的箱子里就放进去尝试一下,然后再在没用过的箱子里面开一个放进去(放进哪一个空箱子都是完全一样的所以只开一个空箱子就行)。可以把物品从大到小排序,即先塞大的物品这样箱子的可用空间会迅速减小然后搜索树就小了。
再说一下dp的做法
f[i] 表示拿的物品状态为i下最少箱子数。
g[i] 下最少箱子数方案中一个箱子的最大剩余量。
把一个不属于状态i的物品j放进去的时候有两种情况:
箱子数不变,需要满足的条件是:g[i]>=w[j]
此时当:f[i|(1<<j)] >= f[i]可以更新f[i|(1<<j)]和g[i|(1<<j)]
f[i|(1<<j)] = f[i]
g[i|(1<<j)] = max(g[i|(1<<j)],g[i]-w[i])
开一个新箱子,
此时当f[i|(1<<j)] >= f[i]+1可以更新f[i|(1<<j)]和g[i|(1<<j)]
f[i|(1<<j)] = f[i]
g[i|(1<<j)] = max(g[i|(1<<j)],W-w[i])

欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目9月1日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴
全部评论
我是第一个,我爱云哥。https://blog.nowcoder.net/n/e8c5e0d1b8a842c6af253e5afcb813f3
点赞 回复 分享
发布于 2020-08-18 12:59
我是第二个,我爱云哥。https://blog.nowcoder.net/n/3ff6dfe108414be1a4c0114fb2d842be
点赞 回复 分享
发布于 2020-08-18 13:54
我是第三个,我爱云哥。https://blog.nowcoder.net/n/26eef8978d554d0f90f871c2e2a0ce2e
点赞 回复 分享
发布于 2020-08-18 14:07
我是第四个,我爱云哥。https://blog.nowcoder.net/n/ce9218455bd94a369becec1ce3a9cb65
点赞 回复 分享
发布于 2020-08-18 14:22
我是第五个,我爱云哥。https://blog.nowcoder.net/n/5f649420a7c241df95e26a9d47eb333f
点赞 回复 分享
发布于 2020-08-18 15:06
我是第六个,我爱云哥。https://blog.nowcoder.net/n/136ed435ff7a4087b61467eb351e97b1
点赞 回复 分享
发布于 2020-08-18 15:49
?????
点赞 回复 分享
发布于 2020-08-18 15:53
https://blog.nowcoder.net/n/bcdbfe6c029e44698cf0014c420b0027
点赞 回复 分享
发布于 2020-08-18 23:23
https://blog.nowcoder.net/n/15b1ff1ea44e4704b29f3b9044f739b3 纯暴力不sort也是500MS 切掉了!
点赞 回复 分享
发布于 2020-08-19 09:32
我是第七个,我爱云哥。https://blog.nowcoder.net/n/e8c96c6278974fdbbf7a89075d98ba22
点赞 回复 分享
发布于 2020-08-19 10:44
https://blog.nowcoder.net/n/6f0f3c80ce6d4b3480aa302d9baf2d22
点赞 回复 分享
发布于 2020-08-19 15:12
https://blog.nowcoder.net/n/bc4c1a579f184e608df3095bf04c5d9c
点赞 回复 分享
发布于 2020-08-19 17:20
https://blog.nowcoder.net/n/7eee668eb8054909982372183b2178c9
点赞 回复 分享
发布于 2020-08-20 16:36
https://blog.nowcoder.net/n/97b71e36e1974baab7d0d922fd661e1c
点赞 回复 分享
发布于 2020-08-21 10:53
https://blog.nowcoder.net/n/ac3caf40e5e5491a8dc945d2d3b6aa15
点赞 回复 分享
发布于 2020-08-27 19:39

相关推荐

nbdy:字太多了,写简历不是写自传,亮点难点技能点列出来就行,要简明扼要
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务