【每日一题】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之前写的题解有获得牛币资格~
牛客博客开通方式
- 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
- 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
- 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴
查看5道真题和解析