2_算法课课件.zip
资源内容介绍
2_算法课课件.zip <link href="/image.php?url=https://csdnimg.cn/release/download_crawler_static/css/base.min.css" rel="stylesheet"/><link href="/image.php?url=https://csdnimg.cn/release/download_crawler_static/css/fancy.min.css" rel="stylesheet"/><link href="/image.php?url=https://csdnimg.cn/release/download_crawler_static/90150446/6/raw.css" rel="stylesheet"/><div id="sidebar" style="display: none"><div id="outline"></div></div><div class="pf w0 h0" data-page-no="1" id="pf1"><div class="pc pc1 w0 h0"><img alt="" class="bi x0 y0 w1 h1" src="/image.php?url=https://csdnimg.cn/release/download_crawler_static/90150446/bg1.jpg"/><div class="c x0 y1 w2 h0"><div class="t m0 x1 h2 y2 ff1 fs0 fc0 sc0 ls0 ws0">动态规划篇：<span class="ff2">0-1</span>背包问题</div><div class="t m0 x2 h3 y3 ff1 fs0 fc0 sc0 ls0 ws0">童咏昕</div><div class="t m0 x3 h4 y4 ff1 fs1 fc0 sc0 ls0 ws0">北京航空航天大学</div><div class="t m0 x2 h4 y5 ff1 fs1 fc0 sc0 ls0 ws0">计算机学院</div><div class="t m0 x4 h4 y6 ff1 fs1 fc0 sc0 ls0 ws0">中国大学<span class="ff3">MOOC</span>北航《算法设计与分析》</div></div><a class="l"><div class="d m1"></div></a><a class="l"><div class="d m1"></div></a></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,0.000000,0.000000]}'></div></div><div id="pf2" class="pf w0 h0" data-page-no="2"><div class="pc pc2 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="/image.php?url=https://csdnimg.cn/release/download_crawler_static/90150446/bg2.jpg"><div class="c x0 y1 w2 h0"><div class="t m0 x5 h5 y7 ff4 fs2 fc1 sc0 ls0 ws0">⚫<span class="_ _0"> </span><span class="ff1 fs3 fc0">超市赢家</span></div><div class="t m0 x6 h6 y8 ff4 fs4 fc2 sc0 ls0 ws0">⚫<span class="_ _1"> </span><span class="ff1 fs1 fc0">超市允许顾客使用一个体积大小为<span class="ff2">13</span>的背包，选择一件或多件商品带走</span></div><div class="t m0 x5 h7 y9 ff1 fs5 fc0 sc0 ls0 ws0">问题背景</div></div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,0.000000,0.000000]}'></div></div><div id="pf3" class="pf w0 h0" data-page-no="3"><div class="pc pc3 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="/image.php?url=https://csdnimg.cn/release/download_crawler_static/90150446/bg3.jpg"><div class="c x0 y1 w2 h0"><div class="t m0 x5 h5 y7 ff4 fs2 fc1 sc0 ls0 ws0">⚫<span class="_ _0"> </span><span class="ff1 fs3 fc0">超市赢家</span></div><div class="t m0 x6 h6 y8 ff4 fs4 fc2 sc0 ls0 ws0">⚫<span class="_ _1"> </span><span class="ff1 fs1 fc0">超市允许顾客使用一个体积大小为<span class="ff2">13</span>的背包，选择一件或多件商品带走</span></div><div class="t m0 x5 h7 y9 ff1 fs5 fc0 sc0 ls0 ws0">问题背景</div><div class="t m0 x7 h8 ya ff1 fs6 fc3 sc1 ls1 ws0">商品<span class="_ _2"> </span>价格<span class="_ _3"> </span>体积</div><div class="t m0 x7 h8 yb ff1 fs6 fc0 sc0 ls0 ws0">啤酒</div><div class="t m0 x8 h9 yc ff2 fs6 fc0 sc0 ls2 ws0">24<span class="_ _4"> </span>10</div><div class="t m0 x7 h8 yd ff1 fs6 fc0 sc0 ls0 ws0">汽水</div><div class="t m0 x9 h9 ye ff2 fs6 fc0 sc0 ls0 ws0">2<span class="_ _5"> </span>3</div><div class="t m0 x7 h8 yf ff1 fs6 fc0 sc0 ls0 ws0">饼干</div><div class="t m0 x9 h9 y10 ff2 fs6 fc0 sc0 ls0 ws0">9<span class="_ _5"> </span>4</div><div class="t m0 x7 h8 y11 ff1 fs6 fc0 sc0 ls0 ws0">面包</div><div class="t m0 x8 h9 y12 ff2 fs6 fc0 sc0 ls2 ws0">10<span class="_ _6"> </span><span class="ls0">5</span></div><div class="t m0 x7 h8 y13 ff1 fs6 fc0 sc0 ls0 ws0">牛奶</div><div class="t m0 x9 h9 y14 ff2 fs6 fc0 sc0 ls0 ws0">9<span class="_ _5"> </span>4</div></div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,0.000000,0.000000]}'></div></div><div id="pf4" class="pf w0 h0" data-page-no="4"><div class="pc pc4 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="/image.php?url=https://csdnimg.cn/release/download_crawler_static/90150446/bg4.jpg"><div class="c x0 y1 w2 h0"><div class="t m0 x5 h5 y7 ff4 fs2 fc1 sc0 ls0 ws0">⚫<span class="_ _0"> </span><span class="ff1 fs3 fc0">超市赢家</span></div><div class="t m0 x6 h6 y8 ff4 fs4 fc2 sc0 ls0 ws0">⚫<span class="_ _1"> </span><span class="ff1 fs1 fc0">超市允许顾客使用一个体积大小为<span class="ff2">13</span>的背包，选择一件或多件商品带走</span></div><div class="t m0 x5 h7 y9 ff1 fs5 fc0 sc0 ls0 ws0">问题背景</div><div class="t m0 xa h5 y15 ff1 fs3 fc0 sc0 ls0 ws0">问题：如何带走总价最多的商品？</div><div class="t m0 x7 h8 ya ff1 fs6 fc3 sc1 ls1 ws0">商品<span class="_ _2"> </span>价格<span class="_ _3"> </span>体积</div><div class="t m0 x7 h8 yb ff1 fs6 fc0 sc0 ls0 ws0">啤酒</div><div class="t m0 x8 h9 yc ff2 fs6 fc0 sc0 ls2 ws0">24<span class="_ _4"> </span>10</div><div class="t m0 x7 h8 yd ff1 fs6 fc0 sc0 ls0 ws0">汽水</div><div class="t m0 x9 h9 ye ff2 fs6 fc0 sc0 ls0 ws0">2<span class="_ _5"> </span>3</div><div class="t m0 x7 h8 yf ff1 fs6 fc0 sc0 ls0 ws0">饼干</div><div class="t m0 x9 h9 y10 ff2 fs6 fc0 sc0 ls0 ws0">9<span class="_ _5"> </span>4</div><div class="t m0 x7 h8 y11 ff1 fs6 fc0 sc0 ls0 ws0">面包</div><div class="t m0 x8 h9 y12 ff2 fs6 fc0 sc0 ls2 ws0">10<span class="_ _6"> </span><span class="ls0">5</span></div><div class="t m0 x7 h8 y13 ff1 fs6 fc0 sc0 ls0 ws0">牛奶</div><div class="t m0 x9 h9 y14 ff2 fs6 fc0 sc0 ls0 ws0">9<span class="_ _5"> </span>4</div></div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,0.000000,0.000000]}'></div></div><div id="pf5" class="pf w0 h0" data-page-no="5"><div class="pc pc5 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="/image.php?url=https://csdnimg.cn/release/download_crawler_static/90150446/bg5.jpg"><div class="c x0 y1 w2 h0"><div class="t m0 x5 h5 y7 ff4 fs2 fc1 sc0 ls0 ws0">⚫<span class="_ _0"> </span><span class="ff1 fs3 fc0">形式化定义</span></div><div class="t m0 x5 h7 y9 ff1 fs5 fc0 sc0 ls0 ws0">问题定义</div><div class="t m0 xb h9 y16 ff2 fs6 fc4 sc0 ls0 ws0">0-1<span class="_"> </span>Knapsack Pr<span class="_ _7"></span>oblem</div><div class="t m0 xb h8 y17 ff1 fs6 fc4 sc0 ls0 ws0">输入</div><div class="t m0 xb ha y18 ff5 fs6 fc0 sc0 ls0 ws0">•<span class="_ _1"> </span><span class="ff6">𝒏<span class="ff1">个商品组成集合</span>𝑶<span class="ff1">，每个商品有两个属性</span>𝒗</span></div><div class="t m0 xc hb y19 ff6 fs7 fc0 sc0 ls0 ws0">𝒊</div><div class="t m0 xd ha y18 ff1 fs6 fc0 sc0 ls0 ws0">和<span class="ff6">𝒑</span></div><div class="t m0 xe hb y19 ff6 fs7 fc0 sc0 ls0 ws0">𝒊</div><div class="t m0 xf h8 y18 ff1 fs6 fc0 sc0 ls0 ws0">，分别表示体积和价格</div><div class="t m0 x10 h6 y1a ff2 fs1 fc3 sc0 ls0 ws0">0-1<span class="ff1">背包问题</span></div></div></div><div class="pi" data-data='{"ctm":[1.000000,0.000000,0.000000,1.000000,0.000000,0.000000]}'></div></div>