{"id":40,"date":"2026-04-05T16:01:57","date_gmt":"2026-04-05T08:01:57","guid":{"rendered":"https:\/\/blog.sjll.top\/?p=40"},"modified":"2026-04-05T16:01:57","modified_gmt":"2026-04-05T08:01:57","slug":"%e8%83%8c%e5%8c%85%e9%97%ae%e9%a2%98%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92%e8%af%a6%e8%a7%a3%ef%bc%9ac%e5%ae%9e%e7%8e%b00-1%e8%83%8c%e5%8c%85%e4%b8%8e%e5%ae%8c%e5%85%a8%e8%83%8c%e5%8c%85","status":"publish","type":"post","link":"https:\/\/www.sjll.top\/?p=40","title":{"rendered":"\u80cc\u5305\u95ee\u9898\u52a8\u6001\u89c4\u5212\u8be6\u89e3\uff1aC++\u5b9e\u73b00-1\u80cc\u5305\u4e0e\u5b8c\u5168\u80cc\u5305"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">\u4ec0\u4e48\u662f\u80cc\u5305\u95ee\u9898\uff1f<\/h2>\n\n\n\n<p><strong>\u80cc\u5305\u95ee\u9898\uff08Knapsack Problem\uff09<\/strong> \u662f\u8ba1\u7b97\u673a\u79d1\u5b66\u4e2d\u7ecf\u5178\u7684\u52a8\u6001\u89c4\u5212\u95ee\u9898\u3002\u7ed9\u5b9a\u4e00\u7ec4\u7269\u54c1\uff0c\u6bcf\u4e2a\u7269\u54c1\u6709\u91cd\u91cf\u548c\u4ef7\u503c\uff0c\u5728\u4e0d\u8d85\u8fc7\u80cc\u5305\u5bb9\u91cf\u7684\u60c5\u51b5\u4e0b\uff0c\u9009\u62e9\u7269\u54c1\u4f7f\u5f97\u603b\u4ef7\u503c\u6700\u5927\u5316\u3002<\/p>\n\n\n\n<p>\u5e38\u89c1\u7684\u80cc\u5305\u95ee\u9898\u7c7b\u578b\u5305\u62ec\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><strong>0-1\u80cc\u5305<\/strong>\uff1a\u6bcf\u79cd\u7269\u54c1\u53ea\u80fd\u90090\u4e2a\u62161\u4e2a<\/li><li><strong>\u5b8c\u5168\u80cc\u5305<\/strong>\uff1a\u6bcf\u79cd\u7269\u54c1\u53ef\u4ee5\u9009\u65e0\u9650\u4e2a<\/li><li><strong>\u591a\u91cd\u80cc\u5305<\/strong>\uff1a\u6bcf\u79cd\u7269\u54c1\u6709\u6570\u91cf\u9650\u5236<\/li><li><strong>\u5206\u7ec4\u80cc\u5305<\/strong>\uff1a\u7269\u54c1\u5206\u7ec4\uff0c\u6bcf\u7ec4\u6700\u591a\u9009\u4e00\u4e2a<\/li><\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">0-1 \u80cc\u5305\u95ee\u9898\u63cf\u8ff0<\/h3>\n\n\n\n<p>\u6709 n \u4ef6\u7269\u54c1\u548c\u4e00\u4e2a\u5bb9\u91cf\u4e3a W \u7684\u80cc\u5305\u3002\u7b2c i \u4ef6\u7269\u54c1\u7684\u91cd\u91cf\u4e3a w[i]\uff0c\u4ef7\u503c\u4e3a v[i]\u3002\u6c42\u89e3\u5c06\u54ea\u4e9b\u7269\u54c1\u88c5\u5165\u80cc\u5305\u53ef\u4f7f\u4ef7\u503c\u603b\u548c\u6700\u5927\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u52a8\u6001\u89c4\u5212\u89e3\u6cd5<\/h3>\n\n\n\n<p>\u5b9a\u4e49 <code>dp[i][w]<\/code> \u8868\u793a\uff1a\u8003\u8651\u524d i \u4ef6\u7269\u54c1\uff0c\u80cc\u5305\u5bb9\u91cf\u4e3a w \u65f6\u7684\u6700\u5927\u4ef7\u503c\u3002<\/p>\n\n\n\n<p>\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>dp[i][w] = max(dp[i-1][w], dp[i-1][w-w[i]] + v[i])<\/code><\/pre>\n\n\n\n<p>\u5373\uff1a\u5bf9\u4e8e\u7b2c i \u4ef6\u7269\u54c1\uff0c\u53ef\u4ee5\u9009\u62e9<strong>\u4e0d\u9009<\/strong>\u6216<strong>\u9009<\/strong>\uff08\u524d\u63d0\u662f\u5bb9\u91cf\u591f\uff09<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">C++ \u4ee3\u7801\u5b9e\u73b0<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\">#include &lt;iostream&gt;\n#include &lt;vector&gt;\nusing namespace std;\n\n\/\/ 0-1 \u80cc\u5305\u4e8c\u7ef4 DP\nint knapsack_2d(vector&lt;int&gt;&amp; weight, vector&lt;int&gt;&amp; value, int W) {\n    int n = weight.size();\n    vector&lt;vector&lt;int&gt;&gt; dp(n + 1, vector&lt;int&gt;(W + 1, 0));\n    \n    for (int i = 1; i &lt;= n; i++) {\n        for (int w = 0; w &lt;= W; w++) {\n            \/\/ \u4e0d\u9009\u7b2c i \u4ef6\u7269\u54c1\n            dp[i][w] = dp[i-1][w];\n            \n            \/\/ \u9009\u7b2c i \u4ef6\u7269\u54c1\uff08\u5bb9\u91cf\u591f\u7684\u60c5\u51b5\u4e0b\uff09\n            if (w &gt;= weight[i-1]) {\n                dp[i][w] = max(dp[i][w], dp[i-1][w - weight[i-1]] + value[i-1]);\n            }\n        }\n    }\n    \n    return dp[n][W];\n}\n\n\/\/ 0-01 \u80cc\u5305\u4e00\u7ef4 DP\uff08\u7a7a\u95f4\u4f18\u5316\uff09\nint knapsack_1d(vector&lt;int&gt;&amp; weight, vector&lt;int&gt;&amp; value, int W) {\n    int n = weight.size();\n    vector&lt;int&gt; dp(W + 1, 0);\n    \n    for (int i = 0; i &lt; n; i++) {\n        \/\/ \u5012\u5e8f\u904d\u5386\uff0c\u786e\u4fdd\u6bcf\u4ef6\u7269\u54c1\u53ea\u9009\u4e00\u6b21\n        for (int w = W; w &gt;= weight[i]; w--) {\n            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);\n        }\n    }\n    \n    return dp[W];\n}\n\n\/\/ \u8bb0\u5f55\u9009\u62e9\u65b9\u6848\nvector&lt;int&gt; knapsack_with_choice(vector&lt;int&gt;&amp; weight, vector&lt;int&gt;&amp; value, int W) {\n    int n = weight.size();\n    vector&lt;vector&lt;int&gt;&gt; dp(n + 1, vector&lt;int&gt;(W + 1, 0));\n    \n    \/\/ \u586b\u5145 DP \u8868\n    for (int i = 1; i &lt;= n; i++) {\n        for (int w = 0; w &lt;= W; w++) {\n            dp[i][w] = dp[i-1][w];\n            if (w &gt;= weight[i-1]) {\n                dp[i][w] = max(dp[i][w], dp[i-1][w - weight[i-1]] + value[i-1]);\n            }\n        }\n    }\n    \n    \/\/ \u56de\u6eaf\u627e\u51fa\u9009\u62e9\u4e86\u54ea\u4e9b\u7269\u54c1\n    vector&lt;int&gt; chosen;\n    int w = W;\n    for (int i = n; i &gt; 0 &amp;&amp; w &gt; 0; i--) {\n        if (dp[i][w] != dp[i-1][w]) {\n            chosen.push_back(i - 1);  \/\/ \u9009\u62e9\u4e86\u7b2c i-1 \u4ef6\u7269\u54c1\n            w -= weight[i-1];\n        }\n    }\n    reverse(chosen.begin(), chosen.end());\n    \n    return chosen;\n}\n\nint main() {\n    int n = 4;\n    vector&lt;int&gt; weight = {2, 3, 4, 5};\n    vector&lt;int&gt; value = {3, 4, 5, 6};\n    int W = 8;\n    \n    cout &lt;&lt; \"\u7269\u54c1\u4fe1\u606f:\" &lt;&lt; endl;\n    for (int i = 0; i &lt; n; i++) {\n        cout &lt;&lt; \"\u7269\u54c1\" &lt;&lt; i &lt;&lt; \": \u91cd\u91cf=\" &lt;&lt; weight[i] &lt;&lt; \", \u4ef7\u503c=\" &lt;&lt; value[i] &lt;&lt; endl;\n    }\n    cout &lt;&lt; \"\u80cc\u5305\u5bb9\u91cf: \" &lt;&lt; W &lt;&lt; endl;\n    \n    cout &lt;&lt; \"\\n\u6700\u5927\u4ef7\u503c (\u4e8c\u7ef4DP): \" &lt;&lt; knapsack_2d(weight, value, W) &lt;&lt; endl;\n    cout &lt;&lt; \"\u6700\u5927\u4ef7\u503c (\u4e00\u7ef4DP): \" &lt;&lt; knapsack_1d(weight, value, W) &lt;&lt; endl;\n    \n    \/\/ \u8f93\u51fa\u9009\u62e9\u4e86\u54ea\u4e9b\u7269\u54c1\n    vector&lt;int&gt; chosen = knapsack_with_choice(weight, value, W);\n    cout &lt;&lt; \"\u9009\u62e9\u7684\u7269\u54c1: \";\n    for (int idx : chosen) {\n        cout &lt;&lt; idx &lt;&lt; \"(w=\" &lt;&lt; weight[idx] &lt;&lt; \",v=\" &lt;&lt; value[idx] &lt;&lt; \") \";\n    }\n    cout &lt;&lt; endl;\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u5b8c\u5168\u80cc\u5305\uff08\u6bcf\u79cd\u7269\u54c1\u65e0\u9650\u4ef6\uff09<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\">\/\/ \u5b8c\u5168\u80cc\u5305\u4e00\u7ef4 DP\nint complete_knapsack(vector&lt;int&gt;&amp; weight, vector&lt;int&gt;&amp; value, int W) {\n    int n = weight.size();\n    vector&lt;int&gt; dp(W + 1, 0);\n    \n    for (int i = 0; i &lt; n; i++) {\n        \/\/ \u6b63\u5e8f\u904d\u5386\uff0c\u5b8c\u5168\u80cc\u5305\u53ef\u4ee5\u91cd\u590d\u9009\n        for (int w = weight[i]; w &lt;= W; w++) {\n            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);\n        }\n    }\n    \n    return dp[W];\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u590d\u6742\u5ea6\u5206\u6790<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table><thead><tr><th>\u65b9\u6cd5<\/th><th>\u65f6\u95f4\u590d\u6742\u5ea6<\/th><th>\u7a7a\u95f4\u590d\u6742\u5ea6<\/th><\/tr><\/thead><tbody><tr><td>\u4e8c\u7ef4 DP<\/td><td>O(n \u00d7 W)<\/td><td>O(n \u00d7 W)<\/td><\/tr><tr><td>\u4e00\u7ef4 DP<\/td><td>O(n \u00d7 W)<\/td><td>O(W)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">\u80cc\u5305\u95ee\u9898\u7684\u53d8\u5f62<\/h3>\n\n\n\n<ol class=\"wp-block-list\"><li><strong>\u591a\u91cd\u80cc\u5305<\/strong>\uff1a\u5c06\u7269\u54c1\u6570\u91cf\u62c6\u5206\u8f6c\u5316\u4e3a 0-1 \u80cc\u5305<\/li><li><strong>\u5206\u7ec4\u80cc\u5305<\/strong>\uff1a\u6bcf\u7ec4\u53ea\u80fd\u9009\u4e00\u4e2a<\/li><li><strong>\u4e8c\u7ef4\u80cc\u5305<\/strong>\uff1a\u4e24\u4e2a\u9650\u5236\u6761\u4ef6\uff08\u5982\u91cd\u91cf\u548c\u4f53\u79ef\uff09<\/li><\/ol>\n\n\n\n<h3 class=\"wp-block-heading\">\u603b\u7ed3<\/h3>\n\n\n\n<p>\u80cc\u5305\u95ee\u9898\u662f\u52a8\u6001\u89c4\u5212\u7684\u7ecf\u5178\u5165\u95e8\u9898\u76ee\u3002\u638c\u63e1 0-1 \u80cc\u5305\u7684\u6838\u5fc3\u601d\u60f3\uff08\u9009\u6216\u4e0d\u9009\uff09\uff0c\u5bf9\u4e8e\u7406\u89e3\u5176\u4ed6\u52a8\u6001\u89c4\u5212\u95ee\u9898\u975e\u5e38\u6709\u5e2e\u52a9\u3002\u7a7a\u95f4\u4f18\u5316\u6280\u5de7\uff08\u4ece\u4e8c\u7ef4\u964d\u5230\u4e00\u7ef4\uff09\u4e5f\u662f\u5e38\u89c1\u7684\u4f18\u5316\u624b\u6bb5\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u4ec0\u4e48\u662f\u80cc\u5305\u95ee\u9898\uff1f \u80cc\u5305\u95ee\u9898\uff08Knapsack Problem\uff09 \u662f\u8ba1\u7b97\u673a\u79d1\u5b66\u4e2d\u7ecf\u5178\u7684\u52a8\u6001\u89c4\u5212\u95ee\u9898\u3002\u7ed9\u5b9a\u4e00\u7ec4\u7269\u54c1 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[49,48],"class_list":["post-40","post","type-post","status-publish","format-standard","hentry","category-3","tag-knapsack-problem","tag-c01"],"_links":{"self":[{"href":"https:\/\/www.sjll.top\/index.php?rest_route=\/wp\/v2\/posts\/40","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.sjll.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.sjll.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.sjll.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.sjll.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=40"}],"version-history":[{"count":1,"href":"https:\/\/www.sjll.top\/index.php?rest_route=\/wp\/v2\/posts\/40\/revisions"}],"predecessor-version":[{"id":47,"href":"https:\/\/www.sjll.top\/index.php?rest_route=\/wp\/v2\/posts\/40\/revisions\/47"}],"wp:attachment":[{"href":"https:\/\/www.sjll.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=40"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.sjll.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=40"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.sjll.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=40"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}