PageSourceSearch

https://consolexinhun-github-io.pages.dev/pages/37ebac/

html consolexinhun-github-io.pages.dev collected 2026-10-03 05:38:39 UTC 44,580 bytes, 146 lines download raw bytes

1<!DOCTYPE html>
2<html lang="en-US">
3  <head>
4    <meta charset="utf-8">
5    <meta name="viewport" content="width=device-width,initial-scale=1">
6    <title>01背包 | Consolexin&#39;s blog</title>
7    <meta name="generator" content="VuePress 1.8.0">
8    <link rel="icon" href="/img/favicon.ico">
9    
9<script data-ad-client="ca-pub-7828333725993554" async="async" src="https://pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
9
10    <meta name="description" content="Consolexin 的 博客">
11    <meta name="keywords" content="个人博客">
12    <meta name="baidu-site-verification" content="7F55weZDDc">
13    <meta name="theme-color" content="#11a8cd">
14    
15    <link rel="preload" href="/assets/css/0.styles.4eac6ea4.css" as="style"><link rel="preload" href="/assets/js/app.bc01e2eb.js" as="script"><link rel="preload" href="/assets/js/2.8ef71c9e.js" as="script"><link rel="preload" href="/assets/js/15.595f1abe.js" as="script"><link rel="prefetch" href="/assets/js/10.515404a1.js"><link rel="prefetch" href="/assets/js/11.4a5a609b.js"><link rel="prefetch" href="/assets/js/12.c4724906.js"><link rel="prefetch" href="/assets/js/13.46a7749d.js"><link rel="prefetch" href="/assets/js/14.236b97a6.js"><link rel="prefetch" href="/assets/js/16.b491f116.js"><link rel="prefetch" href="/assets/js/17.fefd8661.js"><link rel="prefetch" href="/assets/js/18.8ff43b6b.js"><link rel="prefetch" href="/assets/js/19.f5631122.js"><link rel="prefetch" href="/assets/js/20.c2b47c5a.js"><link rel="prefetch" href="/assets/js/21.76cfa96e.js"><link rel="prefetch" href="/assets/js/22.d009171f.js"><link rel="prefetch" href="/assets/js/23.e2b1aa3a.js"><link rel="prefetch" href="/assets/js/24.195f9ca0.js"><link rel="prefetch" href="/assets/js/25.888dd79e.js"><link rel="prefetch" href="/assets/js/26.b770f6fd.js"><link rel="prefetch" href="/assets/js/27.eaf0f1fd.js"><link rel="prefetch" href="/assets/js/28.f4dcf162.js"><link rel="prefetch" href="/assets/js/29.261e430f.js"><link rel="prefetch" href="/assets/js/3.41d5378a.js"><link rel="prefetch" href="/assets/js/30.84c300c4.js"><link rel="prefetch" href="/assets/js/31.f009deb6.js"><link rel="prefetch" href="/assets/js/32.ff56105a.js"><link rel="prefetch" href="/assets/js/33.dde6549f.js"><link rel="prefetch" href="/assets/js/34.0ed3fd66.js"><link rel="prefetch" href="/assets/js/35.b7f79619.js"><link rel="prefetch" href="/assets/js/36.e3b78869.js"><link rel="prefetch" href="/assets/js/37.fc38ab3f.js"><link rel="prefetch" href="/assets/js/38.c324a744.js"><link rel="prefetch" href="/assets/js/39.e8503762.js"><link rel="prefetch" href="/assets/js/4.03adff2f.js"><link rel="prefetch" href="/assets/js/40.55d5afec.js"><link rel="prefetch" href="/assets/js/41.9aa0e112.js"><link rel="prefetch" href="/assets/js/42.83b0f972.js"><link rel="prefetch" href="/assets/js/43.edfda84c.js"><link rel="prefetch" href="/assets/js/44.dba91948.js"><link rel="prefetch" href="/assets/js/45.06dfeab1.js"><link rel="prefetch" href="/assets/js/46.06724fcb.js"><link rel="prefetch" href="/assets/js/47.9cd9b6c0.js"><link rel="prefetch" href="/assets/js/48.f5afa1cb.js"><link rel="prefetch" href="/assets/js/49.813343bf.js"><link rel="prefetch" href="/assets/js/5.51b63341.js"><link rel="prefetch" href="/assets/js/50.202a57f6.js"><link rel="prefetch" href="/assets/js/51.43f876d0.js"><link rel="prefetch" href="/assets/js/52.c4d9a593.js"><link rel="prefetch" href="/assets/js/53.be6b7e63.js"><link rel="prefetch" href="/assets/js/54.ab52ecc6.js"><link rel="prefetch" href="/assets/js/55.760eb0e1.js"><link rel="prefetch" href="/assets/js/56.3549faaf.js"><link rel="prefetch" href="/assets/js/57.4c722c7a.js"><link rel="prefetch" href="/assets/js/58.e1a58d4a.js"><link rel="prefetch" href="/assets/js/59.22a828f2.js"><link rel="prefetch" href="/assets/js/6.7f5d0cd3.js"><link rel="prefetch" href="/assets/js/60.dbb9f1e0.js"><link rel="prefetch" href="/assets/js/61.32c3c486.js"><link rel="prefetch" href="/assets/js/62.773eef44.js"><link rel="prefetch" href="/assets/js/63.fd4a89ff.js"><link rel="prefetch" href="/assets/js/64.0babe661.js"><link rel="prefetch" href="/assets/js/65.79b0a3dc.js"><link rel="prefetch" href="/assets/js/66.6f0337b5.js"><link rel="prefetch" href="/assets/js/67.9b447bcf.js"><link rel="prefetch" href="/assets/js/68.1dd3b45b.js"><link rel="prefetch" href="/assets/js/69.bf0b09fe.js"><link rel="prefetch" href="/assets/js/7.3bdf4e34.js"><link rel="prefetch" href="/assets/js/70.767fee34.js"><link rel="prefetch" href="/assets/js/71.a9e2d44b.js"><link rel="prefetch" href="/assets/js/72.36563e9c.js"><link rel="prefetch" href="/assets/js/73.f933f9b6.js"><link rel="prefetch" href="/assets/js/74.be4e7a5c.js"><link rel="prefetch" href="/assets/js/75.880046a9.js"><link rel="prefetch" href="/assets/js/76.a66fb341.js"><link rel="prefetch" href="/assets/js/77.968dd07c.js"><link rel="prefetch" href="/assets/js/78.dba6a445.js"><link rel="prefetch" href="/assets/js/79.cab34d57.js"><link rel="prefetch" href="/assets/js/8.9ac9ea63.js"><link rel="prefetch" href="/assets/js/80.be7b9ab5.js"><link rel="prefetch" href="/assets/js/81.5ee4d1a9.js"><link rel="prefetch" href="/assets/js/82.42cc1c90.js"><link rel="prefetch" href="/assets/js/83.fabc1535.js"><link rel="prefetch" href="/assets/js/84.559d3801.js"><link rel="prefetch" href="/assets/js/9.ee7b94bb.js">
16    <link rel="stylesheet" href="/assets/css/0.styles.4eac6ea4.css">
17  </head>
18  <body class="theme-mode-light">
19    <div id="app" data-server-rendered="true"><div class="theme-container sidebar-open have-rightmenu have-body-img"><header class="navbar blur"><div title="目录" class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon">
19<path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><img src="/img/EB-logo.png" alt="Consolexin's blog" class="logo"> <span class="site-name can-hide">Consolexin's blog</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/" class="nav-link">首页</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="算法" class="dropdown-title"><a href="/algorithm/" class="link-title">算法</a> <span class="title" style="display:none;">算法</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>算法基础</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/pages/5a514b/" class="nav-link">图论</a></li><li class="dropdown-subitem"><a href="/pages/3ce601/" class="nav-link">字符串</a></li><li class="dropdown-subitem"><a href="/pages/37ebac/" aria-current="page" class="nav-link router-link-exact-active router-link-active">动态规划</a></li><li class="dropdown-subitem"><a href="/pages/cc5f84/" class="nav-link">二分</a></li><li class="dropdown-subitem"><a href="/pages/30b0a0/" class="nav-link">滑动窗口</a></li><li class="dropdown-subitem"><a href="/pages/a0391b/" class="nav-link">排序</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="C++" class="dropdown-title"><a href="/cplusplus/" class="link-title">C++</a> <span class="title" style="display:none;">C++</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>Project</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/CppServer/" class="nav-link">CppServer</a></li></ul></li><li class="dropdown-item"><h4>相关书籍</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/modern_cpp_programming/" class="nav-link">现代C++编程</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="SQL" class="dropdown-title"><a href="/sql/" class="link-title">SQL</a> <span class="title" style="display:none;">SQL</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>书籍</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/pages/eef00a/" class="nav-link">SQL必知必会</a></li><li class="dropdown-subitem"><a href="/pages/fbcf66/" class="nav-link">MySQL必知必会</a></li></ul></li></ul></div></div><div class="nav-item"><a href="/categories/" class="nav-link">分类</a></div><div class="nav-item"><a href="/tags/" class="nav-link">标签</a></div><div class="nav-item"><a href="/archives/" class="nav-link">归档</a></div> <a href="https://github.com/consolexinhun" target="_blank" rel="noopener noreferrer" class="repo-link">
20    GitHub
21    <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask"></div> <div class="sidebar-hover-trigger"></div> <aside class="sidebar" style="display:none;"><div class="blogger"><img src="/img/EB-logo.png"> <div class="blogger-info"><h3>Consolexinhun</h3> <span>小学生</span></div></div> <nav class="nav-links"><div class="nav-item"><a href="/" class="nav-link">首页</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="算法" class="dropdown-title"><a href="/algorithm/" class="link-title">算法</a> <span class="title" style="display:none;">算法</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>算法基础</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/pages/5a514b/" class="nav-link">图论</a></li><li class="dropdown-subitem"><a href="/pages/3ce601/" class="nav-link">字符串</a></li><li class="dropdown-subitem"><a href="/pages/37ebac/" aria-current="page" class="nav-link router-link-exact-active router-link-active">动态规划</a></li><li class="dropdown-subitem"><a href="/pages/cc5f84/" class="nav-link">二分</a></li><li class="dropdown-subitem"><a href="/pages/30b0a0/" class="nav-link">滑动窗口</a></li><li class="dropdown-subitem"><a href="/pages/a0391b/" class="nav-link">排序</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="C++" class="dropdown-title"><a href="/cplusplus/" class="link-title">C++</a> <span class="title" style="display:none;">C++</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>Project</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/CppServer/" class="nav-link">CppServer</a></li></ul></li><li class="dropdown-item"><h4>相关书籍</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/modern_cpp_programming/" class="nav-link">现代C++编程</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="SQL" class="dropdown-title"><a href="/sql/" class="link-title">SQL</a> <span class="title" style="display:none;">SQL</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>书籍</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/pages/eef00a/" class="nav-link">SQL必知必会</a></li><li class="dropdown-subitem"><a href="/pages/fbcf66/" class="nav-link">MySQL必知必会</a></li></ul></li></ul></div></div><div class="nav-item"><a href="/categories/" class="nav-link">分类</a></div><div class="nav-item"><a href="/tags/" class="nav-link">标签</a></div><div class="nav-item"><a href="/archives/" class="nav-link">
21归档</a></div> <a href="https://github.com/consolexinhun" target="_blank" rel="noopener noreferrer" class="repo-link">
22    GitHub
23    <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav>  <ul class="sidebar-links"><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>图论</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>字符串</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading open"><span>动态规划</span> <span class="arrow down"></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/pages/37ebac/" aria-current="page" class="active sidebar-link">01背包</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header level2"><a href="/pages/37ebac/#思路" class="sidebar-link">思路</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header level3"><a href="/pages/37ebac/#二维数组" class="sidebar-link">二维数组</a></li><li class="sidebar-sub-header level3"><a href="/pages/37ebac/#滚动数组优化" class="sidebar-link">滚动数组优化</a></li></ul></li><li class="sidebar-sub-header level2"><a href="/pages/37ebac/#题目" class="sidebar-link">题目</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header level3"><a href="/pages/37ebac/#hdu-2602" class="sidebar-link">HDU 2602</a></li></ul></li><li class="sidebar-sub-header level2"><a href="/pages/37ebac/#参考链接" class="sidebar-link">参考链接</a></li></ul></li><li><a href="/pages/0f9774/" class="sidebar-link">完全背包</a></li><li><a href="/pages/e88894/" class="sidebar-link">多重背包</a></li></ul></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>二分</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>滑动窗口</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>排序</span> <span class="arrow right"></span></p> <!----></section></li></ul> <div class="sidebar-slot sidebar-slot-bottom"><!-- 正方形 -->
24      <ins class="adsbygoogle"
25          style="display:block"
26          data-ad-client="ca-pub-7828333725993554"
27          data-ad-slot="3508773082"
28          data-ad-format="auto"
29          data-full-width-responsive="true"></ins>
30      
30<script>
31          (adsbygoogle = window.adsbygoogle || []).push({});
32      </script>
32</div></aside> <div><main class="page"><div class="theme-vdoing-wrapper "><div class="articleInfo-wrap" data-v-06225672><div class="articleInfo" data-v-06225672><ul class="breadcrumbs" data-v-06225672><li data-v-06225672><a href="/" title="首页" class="iconfont icon-home router-link-active" data-v-06225672></a></li> <li data-v-06225672><a href="/algorithm/#算法" data-v-06225672>算法</a></li><li data-v-06225672><a href="/algorithm/#动态规划" data-v-06225672>动态规划</a></li></ul> <div class="info" data-v-06225672><div title="作者" class="author iconfont icon-touxiang" data-v-06225672><a href="https://github.com/consolexinhun" target="_blank" title="作者" class="beLink" data-v-06225672>consolexinhun</a></div> <div title="创建时间" class="date iconfont icon-riqi" data-v-06225672><a href="javascript:;" data-v-06225672>2021-11-02</a></div> <!----></div></div></div> <!----> <div class="content-wrapper"><div class="right-menu-wrapper"><div class="right-menu-margin"><div class="right-menu-title">目录</div> <div class="right-menu-content"></div></div></div> <h1><img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAB4AAAAeCAYAAAA7MK6iAAAAAXNSR0IArs4c6QAABKFJREFUSA3tVl1oFVcQnrMbrak3QUgkya1akpJYcrUtIqW1JvFBE9LiQ5v6JmJpolbMg32rVrhgoYK0QiMY6i9Y6EMaW5D+xFJaTYItIuK2Kr3+BJNwkxBj05sQY3b3nM6cs2dv9t7NT/vQJw/sndk5M/PNzJkzewGerP+pAmy+ON8lLzUJgA8ZYxYIYZmGYRnctDaWvJJAmTtfP1pvXsBCCPP8QFcCaRkZYACgDZFO4stNIcBCajEOlmmC9XpJ9bAGCaPaPmzPl32dvLSVu3BWCTQs0XQQ6g0DYgwLIoAZbBCdW/i+781o1VVlm/410mw4h06Y7bIPHNyWDyL4FHkX03Q8SrzNhZTZriieckWt7cL6MM85YcLpsi/7O9/iXFT6MswI0DmmpkSaJ0qLxFIm3+i1THHB3zmBH3PYx9CcykcLOeQVVa7QtdxTgQgEleX2AjHYfwA+2ddV77ruGoJUbhGDI09YSNXyMpUt5ylOzxgbUmtOp7NmbNt8v3arjTBfYELmLUV+M+nSawNNAUqpT3ClJWg5I3BLT+cGW/DXNGCa6tx1aakCGEigArTn4TDIPdrXXYKCZNrHLMCOEPvHBlLQ99s9eHB7EB6NTki73CVPQ2F5MSx/uRQixfmq7rK0wYD8w8E905bnPDfwoWs/rfv93NWN/ZfvwsLIU7A09gxECyISeGJkHAau98L97tuw7NXnoPyNF8FcYGLGKsOs0mN3OEyec9esGW/ZEl945dTP34wlR2FZVQWU1q0Cw8Tr7p+hgLLNL0FPxx/Q35mA8aEUrH6nCgwEl0tn7wUiZYJnNRh6DK4UH/k0lfyrsBKdPVv/AriGIQcEDQZ65LBAGe2Rzui9Ybjz7XUppz1/uKBbyVPGkN3ZAeC6hr0x7Nr38N5+EqkoOm17xpoqR9ohQF55ERSvr4Dkr3chNfC3DMzGJlNBElW8w9nsGQvhNGIzDkXzCg8cLK951xHsFBlTJspJNi3ZFIMF2AeDV3q8DNOB+YHi6QTrChDIWDBRi5U5f+ZMfJLu3ccrqxtdxk4SKH336LFxSmkqefwU5T8fhdSdQf9IVKD6aNiwI/hnmcAZ91isYMJIaCUCx9W098+LgruikeTqzqqxKPUwqJyCPJiyemVVZBOijDGjD38Os0jOiSPL1z3SPjXNANbiNPXAdzTfukjjuknNBbyz3nwgTd3AVFqUJ5hpHlq9MveLnWwttUfoygBmvVjuikxND3znrhsELnZk7k+OjIGxeNEkomyLVta0xxn+HZhjBc4YZ/AFjHjz9u3xRZl2BN4aq9nFwWh16IrQ1aHHEd3j1+4/dB9OtH4e29A2H1DyHQRmOSfQZ1Fy7MHBTGB6J/Djq6p3OxyO2cB+4Car7v/o3GXgfAkj23+x9ID1Teoamo/SXcbvSf2PX7Vc8DdCmE1vN9di+32P9/5YR3vLnhCVGUWBjEkr3yh4H8v9CzmsbdhzOKzsJKM90iFdaTMjRPhGVsakRvOaRidljo6H6G7j+ctrJpsP+4COhDIl0La2+FS4+5mlocBaXY5QnGZysIBYoeSsl5qQzrSj/cgNrfuEzlWBfwA+EjrZyWUvpAAAAABJRU5ErkJggg==">01背包<!----></h1> <div class="page-slot page-slot-top"><!-- 固定100% * 90px可显示,max-height:90px未见显示-->
33     <ins class="adsbygoogle"
34          style="display:inline-block;width:100%;max-height:90px"
35          data-ad-client="ca-pub-7828333725993554"
36          data-ad-slot="6625304284"></ins>
37      
37<script>
38          (adsbygoogle = window.adsbygoogle || []).push({});
39      </script>
39</div> <div class="theme-vdoing-content content__default"><h2 id="思路"><a href="#思路" class="header-anchor">#</a> 思路</h2> <h3 id="二维数组"><a href="#二维数组" class="header-anchor">#</a> 二维数组</h3> <p><img src="https://gitee.com/consolecode/blog-img/raw/master/20211102222826.png" alt=""></p> <div class="custom-block note"><p class="custom-block-title">笔记</p> <p>base case: 都初始化为 0</p></div> <div class="custom-block tip"><p class="custom-block-title">提示</p> <p>遍历顺序:可以先遍历物品再遍历背包,也可以先遍历背包再遍历物品</p></div> <h3 id="滚动数组优化"><a href="#滚动数组优化" class="header-anchor">#</a> 滚动数组优化</h3> <p><img src="https://gitee.com/consolecode/blog-img/raw/master/20211102231752.png" alt=""></p> <h2 id="题目"><a href="#题目" class="header-anchor">#</a> 题目</h2> <h3 id="hdu-2602"><a href="#hdu-2602" class="header-anchor">#</a> HDU 2602</h3> <p>https://acm.hdu.edu.cn/showproblem.php?pid=2602</p> <p>先输入有多少个物品,然后是总容量</p> <p>前一行是物品价值,后一行是物品容量</p> <h4 id="二维数组-2"><a href="#二维数组-2" class="header-anchor">#</a> 二维数组</h4> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;iostream&gt;</span></span>
40<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;algorithm&gt;</span></span>
41<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;vector&gt;</span></span>
42
43<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
44
45<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
46    <span class="token keyword">int</span> T<span class="token punctuation">;</span>
47    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span> <span class="token operator">&amp;</span>T<span class="token punctuation">)</span><span class="token punctuation">;</span>
48    <span class="token keyword">while</span><span class="token punctuation">(</span>T<span class="token operator">--</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
49        <span class="token keyword">int</span> n<span class="token punctuation">,</span> m<span class="token punctuation">;</span>
50        <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d %d&quot;</span><span class="token punctuation">,</span> <span class="token operator">&amp;</span>n<span class="token punctuation">,</span> <span class="token operator">&amp;</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
51
52        vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">w</span><span class="token punctuation">(</span>n<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token function">v</span><span class="token punctuation">(</span>n<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
53        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span> <span class="token operator">&amp;</span>v<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
54        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span> <span class="token operator">&amp;</span>w<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
55
56
57        vector<span class="token operator">&lt;</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token operator">&gt;</span> <span class="token function">dp</span><span class="token punctuation">(</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token generic-function"><span class="token function">vector</span><span class="token generic class-name"><span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span></span></span><span class="token punctuation">(</span>m<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
58        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
59            <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;=</span> m<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
60                <span class="token keyword">if</span><span class="token punctuation">(</span>w<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">&gt;</span> j<span class="token punctuation">)</span> dp<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
61                <span class="token keyword">else</span><span class="token punctuation">{</span>
62                    dp<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token operator">-</span>w<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">+</span> v<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
63                <span class="token punctuation">}</span>
64            <span class="token punctuation">}</span>
65        <span class="token punctuation">}</span>
66        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d\n&quot;</span><span class="token punctuation">,</span> dp<span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token punctuation">[</span>m<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
67    <span class="token punctuation">}</span>
68
69    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
70<span class="token punctuation">}</span>
71<span class="token comment">// 01 背包 2602</span>
72<span class="token comment">// 完全背包 1114</span>
73</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br></div></div><h4 id="滚动数组"><a href="#滚动数组" class="header-anchor">#</a> 滚动数组</h4> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;iostream&gt;</span></span>
74<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;algorithm&gt;</span></span>
75<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;vector&gt;</span></span>
76
77<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
78
79<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
80    <span class="token keyword">int</span> T<span class="token punctuation">;</span>
81    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span> <span class="token operator">&amp;</span>T<span class="token punctuation">)</span><span class="token punctuation">;</span>
82    <span class="token keyword">while</span><span class="token punctuation">(</span>T<span class="token operator">--</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
83        <span class="token keyword">int</span> n<span class="token punctuation">,</span> m<span class="token punctuation">;</span>
84        <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d %d&quot;</span><span class="token punctuation">,</span> <span class="token operator">&amp;</span>n<span class="token punctuation">,</span> <span class="token operator">&amp;</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
85
86        vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">w</span><span class="token punctuation">(</span>n<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token function">v</span><span class="token punctuation">(</span>n<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
87        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span> <span class="token operator">&amp;</span>v<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
88        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">&quot;%d&quot;</span><span class="token punctuation">,</span> <span class="token operator">&amp;</span>w<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
89
90
91        vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">dp</span><span class="token punctuation">(</span>m<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
92        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
93            <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> m<span class="token punctuation">;</span> j <span class="token operator">&gt;=</span> <span class="token number">0</span><span class="token punctuation">;</span> j<span class="token operator">--</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
94                <span class="token keyword">if</span><span class="token punctuation">(</span>w<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">&lt;=</span> j<span class="token punctuation">)</span> <span class="token comment">// 由于存在物品重量为 0 的情况</span>
95                    dp<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span> dp<span class="token punctuation">[</span>j<span class="token operator">-</span>w<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">+</span> v<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
96            <span class="token punctuation">}</span>
97        <span class="token punctuation">}</span>
98        <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;%d\n&quot;</span><span class="token punctuation">,</span> dp<span class="token punctuation">[</span>m<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
99    <span class="token punctuation">}</span>
100
101    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
102<span class="token punctuation">}</span>
103
104
105</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br></div></div><h2 id="参考链接"><a href="#参考链接" class="header-anchor">#</a> 参考链接</h2> <p><a href="https://www.kancloud.cn/kancloud/pack/70124" target="_blank" rel="noopener noreferrer">背包九讲<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p></div></div> <div class="page-slot page-slot-bottom"><!-- 横向自适应 -->
106      <ins class="adsbygoogle"
107          style="display:block"
108          data-ad-client="ca-pub-7828333725993554"
109          data-ad-slot="6620245489"
110          data-ad-format="auto"
111          data-full-width-responsive="true"></ins>
112      
112<script>
113          (adsbygoogle = window.adsbygoogle || []).push({});
114      </script>
114</div> <div class="page-edit"><div class="edit-link"><a href="https://github.com/consolexinhun/edit/master/docs/01.算法/010.动态规划/001.01背包.md" target="_blank" rel="noopener noreferrer">编辑</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <!----> <div class="last-updated"><span class="prefix">上次更新:</span> <span class="time">2025/05/21, 06:42:57</span></div></div> <div class="page-nav-wapper"><div class="page-nav-centre-wrap"><a href="/pages/3ce601/" class="page-nav-centre page-nav-centre-prev"><div class="tooltip">KMP算法</div></a> <a href="/pages/0f9774/" class="page-nav-centre page-nav-centre-next"><div class="tooltip">完全背包</div></a></div> <div class="page-nav"><p class="inner"><span class="prev">
115        ←
116        <a href="/pages/3ce601/" class="prev">KMP算法</a></span> <span class="next"><a href="/pages/0f9774/">完全背包</a>→
117      </span></p></div></div></div> <div class="article-list"><div class="article-title"><a href="/archives/" class="iconfont icon-bi">最近更新</a></div> <div class="article-wrapper"><dl><dd>01</dd> <dt><a href="/pages/00ced5/"><div>
118            6-其他操作
119            <!----></div></a> <span class="date">05-20</span></dt></dl><dl><dd>02</dd> <dt><a href="/pages/e433a0/"><div>
120            4-联结
121            <!----></div></a> <span class="date">05-20</span></dt></dl><dl><dd>03</dd> <dt><a href="/pages/73f56b/"><div>
122            7-管理
123            <!----></div></a> <span class="date">05-20</span></dt></dl> <dl><dd></dd> <dt><a href="/archives/" class="more">更多文章&gt;</a></dt></dl></div></div></main></div> <div class="footer"><div class="icons"><a href="mailto:[email protected]" title="发邮件" target="_blank" class="iconfont icon-youjian"></a><a href="https://github.com/consolexinhun" title="GitHub" target="_blank" class="iconfont icon-github"></a><a href="https://music.163.com/#/playlist?id=755597173" title="听音乐" target="_blank" class="iconfont icon-erji"></a></div> 
124  Theme by
125  <a href="https://github.com/xugaoyi/vuepress-theme-vdoing" target="_blank" title="本站主题">Vdoing</a> 
126    | Copyright © 2019-2025
127    <span>Consolexinhun | <a href="https://github.com/consolexinhun" target="_blank">MIT License</a></span></div> <div class="buttons"><div title="返回顶部" class="button blur go-to-top iconfont icon-fanhuidingbu" style="display:none;"></div> <div title="去评论" class="button blur go-to-comment iconfont icon-pinglun" style="display:none;"></div> <div title="主题模式" class="button blur theme-mode-but iconfont icon-zhuti"><ul class="select-box" style="display:none;"><li class="iconfont icon-zidong">
128          跟随系统
129        </li><li class="iconfont icon-rijianmoshi">
130          浅色模式
131        </li><li class="iconfont icon-yejianmoshi">
132          深色模式
133        </li><li class="iconfont icon-yuedu">
134          阅读模式
135        </li></ul></div></div> <div class="body-bg" style="background:url() center center / cover no-repeat;opacity:0.5;"></div> <!----> <div class="custom-html-window custom-html-window-rb" style="display:;"><div class="custom-wrapper"><span class="close-but">×</span> <div><!-- 固定160*160px -->
136      <ins class="adsbygoogle"
137          style="display:inline-block;max-width:160px;max-height:160px"
138          data-ad-client="ca-pub-7828333725993554"
139          data-ad-slot="8377369658"></ins>
140      
140<script>
141          (adsbygoogle = window.adsbygoogle || []).push({});
142      </script>
142
143      </div></div></div></div><div class="global-ui"><div></div></div></div>
144    
144<script src="/assets/js/app.bc01e2eb.js" defer></script>
144<script src="/assets/js/2.8ef71c9e.js" defer></script>
144<script src="/assets/js/15.595f1abe.js" defer></script>
144
145  </body>
146</html>

Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.