2_算法课课件.zip
资源文件列表:

分治/
分治/02-分而治之篇_归并排序.pdf 2.93MB
分治/03-分而治之篇-递归式求解.pdf 1.16MB
分治/04-分而治之篇-最大子数组问题I.pdf 2.14MB
分治/05-分而治之篇-逆序对计数问题.pdf 1.62MB
分治/06-分而治之篇-快速排序.pdf 1.37MB
分治/07-分而治之篇-次序选择问题.pdf 1.7MB
动态规划/
动态规划/08-动态规划篇-0-1背包问题.pdf 3.32MB
动态规划/09-动态规划篇-最大子数组问题II.pdf 1.73MB
动态规划/10-动态规划篇-最长公共子序列问题.pdf 2.32MB
动态规划/11-动态规划篇-最长公共子串问题.pdf 1.45MB
动态规划/12-动态规划篇-编辑距离问题.pdf 2.23MB
动态规划/13-动态规划篇-钢条切割问题.pdf 1.37MB
动态规划/14-动态规划篇-矩阵链乘法问题.pdf 1.56MB
贪心/
贪心/15-贪心策略篇-部分背包问题.pdf 792.65KB
贪心/16-贪心策略篇-霍夫曼编码.pdf 1.18MB
贪心/17-贪心策略篇-活动选择问题.pdf 2.11MB
资源介绍:
2_算法课课件.zip
⚫ 超市赢家
⚫ 超市允许顾客使用一个体积大小为13的背包,选择一件或多件商品带走
问题背景

⚫ 超市赢家
⚫ 超市允许顾客使用一个体积大小为13的背包,选择一件或多件商品带走
问题背景
商品 价格 体积
啤酒
24 10
汽水
2 3
饼干
9 4
面包
10 5
牛奶
9 4

⚫ 超市赢家
⚫ 超市允许顾客使用一个体积大小为13的背包,选择一件或多件商品带走
问题背景
问题:如何带走总价最多的商品?
商品 价格 体积
啤酒
24 10
汽水
2 3
饼干
9 4
面包
10 5
牛奶
9 4

⚫ 形式化定义
问题定义
0-1 Knapsack Problem
输入
• 𝒏个商品组成集合𝑶,每个商品有两个属性𝒗
𝒊
和𝒑
𝒊
,分别表示体积和价格
0-1背包问题