一亩三分地

 找回密码 注册账号

扫描二维码登录本站


Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
把贵司信息放这里
查看: 1791|回复: 11
收起左侧

[动态规划] 背包问题全解(背包九讲)

[复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   100% (81)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
偶然看到了一个非常好的学习背包相关动态规划的资料,基本涵盖了背包问题的所有内容。跟大家分享,希望有帮助,如果觉得有用也求留个米~

作者 崔添翼
背包问题九讲2.0 beta1.2
https://github.com/tianyicui/pack

1 01 背包问题3
1.1 题目. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 基本思路. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 优化空间复杂度. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 初始化的细节问题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 一个常数优化. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.6 小结. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 完全背包问题5
2.1 题目. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 基本思路. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 一个简单有效的优化. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4 转化为01 背包问题求解. . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.5 O(V N) 的算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.6 小结. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 多重背包问题7
3.1 题目. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 基本算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3 转化为01 背包问题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.4 可行性问题O(V N) 的算法. . . . . . . . . . . . . . . . . . . . . . . . . . 8
*a.k.a. dd_engi
†Build 20120508120900
1
3.5 小结. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4 混合三种背包问题9
4.1 问题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2 01 背包与完全背包的混合. . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.3 再加上多重背包. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.4 小结. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5 二维费用的背包问题10
5.1 问题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.2 算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.3 物品总个数的限制. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.4 复整数域上的背包问题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.5 小结. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
6 分组的背包问题11
6.1 问题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
6.2 算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
6.3 小结. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
7 有依赖的背包问题12
7.1 简化的问题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
7.2 算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
7.3 较一般的问题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
7.4 小结. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
8 泛化物品13
8.1 定义. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
8.2 泛化物品的和. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
8.3 背包问题的泛化物品. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
8.4 小结. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
9 背包问题问法的变化14
9.1 输出方案. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
9.2 输出字典序最小的最优方案. . . . . . . . . . . . . . . . . . . . . . . . . . 15
9.3 求方案总数. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
9.4 最优方案的总数. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
9.5 求次优解、第K 优解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
9.6 小结. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

评分

参与人数 11大米 +45 收起 理由
llwc + 3 给你点个赞!
gyuanrui + 2 很有用的信息!三连了!
艾利克斯 + 3 给你点个赞!
mountainHigh + 2 很有用的信息!
park02 + 25 很有用的信息!
fdbyxxx + 1 很有用的信息!
chaowei666 + 2 很有用的信息!
dorismeixing + 2 给你点个赞!
dovedove + 1 赞一个
bobcat_mtnlion + 2 给你点个赞!

查看全部评分


上一篇:Leetcode 268. Missing Number,run time complexity
下一篇:【刷上课】Data Structures and Performance by UC San Diego
我的人缘0
esanio 2019-7-17 15:32:53 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
这个很有用,谢谢分享。
回复

使用道具 举报

我的人缘0
312500083 2019-7-17 17:33:05 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   86% (97)
 
 
13% (15)    👎
正好在看背包,感谢楼主!
回复

使用道具 举报

我的人缘0
yanjinbin 2019-9-11 19:45:17 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (40)
 
 
0% (0)    👎
请问下 楼主 你现在发的背包问题是全的吗?  是目前最新修改版本吗?   
回复

使用道具 举报

我的人缘0
yanjinbin 2019-9-11 20:32:00 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (40)
 
 
0% (0)    👎
看到了 崔添翼 是个 大佬   
回复

使用道具 举报

我的人缘0
zdj199583 2019-9-12 14:25:31 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   55% (76)
 
 
44% (61)    👎
yanjinbin 发表于 2019-9-11 20:32
看到了 崔添翼 是个 大佬

是不是逐渐都会抛弃leetcode转向noip母题?
回复

使用道具 举报

我的人缘0
yanjinbin 2019-9-12 14:40:37 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (40)
 
 
0% (0)    👎
zdj199583 发表于 2019-9-12 14:25
是不是逐渐都会抛弃leetcode转向noip母题?

不太清楚 我觉得不会  企业招人 拿 leetcode 作为一杆尺子 已经 能达到筛选人的标准了,
作为面试者 蜗觉得没必要 上纲上线到NOIP的题目 吧
崔添翼  jane street  香港 本科毕业 100w年薪
当时 学校论坛还很轰动   
直到  我看到DP 九讲之后  我一搜 才知道 原来是那位大佬  

我看了V2版本    我觉得 如他所说  理解他的这篇 写作  也需要花费很长时间的  


回复

使用道具 举报

我的人缘0
miaoxinhuili 2019-9-13 01:12:46 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (44)
 
 
0% (0)    👎
谢谢分享 祝福祝福
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版||一亩三分地

GMT+8, 2019-10-22 15:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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