首页 > 其他 > 详细

装载问题(01背包)

时间:2021-05-17 22:40:00      阅读:27      评论:0      收藏:0      [点我收藏+]

1.问题

技术分享图片

2.解析

思路:背包(dp)

也就是最朴素的01背包问题

dp[j]就表示当下表为j的时候所能装载 的最大数量,可以得到dp的状态转移方程
dp[j]=max(dp[j],dp[j-a[i]]+1);(i从1~n 也就是所有的物品)

思路:贪心

想法:每次都选择重量最小的添加到其中

技术分享图片

 

 技术分享图片

 

 

3.设计

dp:

技术分享图片

 

 贪心:

技术分享图片

 

 

4.分析

dp的时间复杂度复杂度O(n*log n)//n是背包的数目,m背包的容量

贪心的时间复杂度O(n*logn)

5.源码

GitHub

装载问题(01背包)

原文:https://www.cnblogs.com/passawayy/p/14777261.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!