{"id":603,"date":"2023-03-15T16:17:26","date_gmt":"2023-03-15T08:17:26","guid":{"rendered":"https:\/\/lolife.top\/?p=603"},"modified":"2023-03-15T16:17:27","modified_gmt":"2023-03-15T08:17:27","slug":"%e8%83%8c%e5%8c%85%e9%97%ae%e9%a2%98-01%e8%83%8c%e5%8c%85","status":"publish","type":"post","link":"https:\/\/lolife.top\/?p=603","title":{"rendered":"\u80cc\u5305\u95ee\u9898\u2014\u201401\u80cc\u5305"},"content":{"rendered":"\n

\u9898\u76ee<\/strong><\/h2>\n\n\n\n

\u6700\u57fa\u672c\u7684\u80cc\u5305\u95ee\u9898\u5c31\u662f01\u80cc\u5305\u95ee\u9898\uff0801 knapsack problem\uff09\uff1a\u4e00\u5171\u6709N\u4ef6\u7269\u54c1\uff0c\u7b2ci\uff08i\u4ece1\u5f00\u59cb\uff09\u4ef6\u7269\u54c1\u7684\u91cd\u91cf\u4e3aw[i]\uff0c\u4ef7\u503c\u4e3av[i]\u3002\u5728\u603b\u91cd\u91cf\u4e0d\u8d85\u8fc7\u80cc\u5305\u627f\u8f7d\u4e0a\u9650W\u7684\u60c5\u51b5\u4e0b\uff0c\u80fd\u591f\u88c5\u5165\u80cc\u5305\u7684\u6700\u5927\u4ef7\u503c\u662f\u591a\u5c11\uff1f<\/p>\n\n\n\n

\u5206\u6790<\/strong><\/p>\n\n\n\n

\u5bf9\u4e8e\u6bcf\u4ef6\u7269\u54c1\uff0c\u6211\u4eec\u90fd\u6709\u53d6\u548c\u4e0d\u53d6\u4e24\u79cd\u4e24\u79cd\u60c5\u51b5\uff0c\u6240\u4ee5\u6211\u4eec\u5b9a\u4e49\u72b6\u6001dp\uff1a<\/p>\n\n\n\n

dp[i][j]\/\/\u8868\u793a\u53ea\u8003\u8651\u524di\u4ef6\u7269\u4f53\u3001\u4f53\u79ef\u4e3aj\u7684\u60c5\u51b5\u4e0b\u80cc\u5305\u7684\u6700\u5927\u4ef7\u503c<\/code><\/pre>\n\n\n\n
\u6211\u4eec\u5c06dp[0][0…w]\u521d\u59cb\u5316\u4e3a0\uff0c\u56e0\u4e3a\u8fd9\u8868\u793a\u7684\u662f\u8003\u8651\u524d0\u4ef6\u7269\u54c1\u7684\u60c5\u51b5\u4e0b\u80cc\u5305\u7684\u6700\u5927\u4ef7\u503c\uff0c\u6ca1\u6709\u7269\u54c1\uff0c\u4e5f\u5c31\u6ca1\u6709\u4ef7\u503c\uff1b<\/p>\n\n\n\n
\u540c\u6837\u5c06dp[0…n][0]\u521d\u59cb\u5316\u4e3a0\uff0c\u8868\u793a\u7684\u662f\u8003\u8651\u4f53\u79ef\u4e3a0\u7684\u60c5\u51b5\u4e0b\u80cc\u5305\u7684\u6700\u5927\u4ef7\u503c\uff0c\u6ca1\u6709\u4f53\u79ef\uff0c\u540c\u6837\u6ca1\u6709\u4ef7\u503c\uff1b<\/p>\n\n\n\n
\u90a3\u4e48\u5f53i>0\u65f6\uff0cdp[i][j]\u6709\u4e24\u79cd\u60c5\u51b5\uff1a<\/p>\n\n\n\n
    \n
  • \u88c5\u5165\u7b2ci\u4ef6\u7269\u54c1\uff1adp[i][j]=v[i]+dp[i-1][j-w[i]];         \/\/j-w[i]\u6307\u88c5\u5b8c\u7b2ci\u4ef6\u7269\u54c1\u540e\u5269\u4f59\u4f53\u79ef<\/li>\n\n\n\n
  • \u4e0d\u88c5\u5165\u7b2ci\u4ef6\u7269\u54c1\uff1adp[i][j]=dp[i-1][j];<\/li>\n<\/ul>\n\n\n\n
    \u6240\u4ee5\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u4e3a\uff1a<\/p>\n\n\n\n
    dp[i][j] = max(dp[i\u22121][j], dp[i\u22121][j\u2212w[i]]+v[i]) \/\/ j >= w[i]<\/code><\/pre>\n\n\n\n
    \u6838\u5fc3\u4ee3\u7801\uff1a<\/p>\n\n\n\n
    for (int i=1;i<=N;i++)\r\n\t{\r\n\t\tfor (int j=0;j<=W;j++)\r\n\t\t{\r\n\t\t\tif (j>=w[i])\r\n\t\t\t{\r\n\t\t\t\tdp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);\r\n\t\t\t}\r\n\t\t\telse\r\n\t\t\t{\r\n\t\t\t\tdp[i][j] = dp[i - 1][j];\r\n\t\t\t}\r\n\t\t}\r\n\t}<\/code><\/pre>\n\n\n\n
    \u4f18\u5316<\/strong><\/p>\n\n\n\n
    \u6211\u4eec\u53ef\u4ee5\u53d1\u73b0\uff0c\u5f53\u6211\u4eec\u5faa\u73afi\u4ef6\u7269\u54c1\u65f6\uff0c\u5e76\u4e0d\u4f1a\u7528\u5230i-2\u4ef6\u7269\u54c1\u65f6\u7684\u6570\u636e;<\/p>\n\n\n\n
    \u5e76\u4e14\u5982\u679c\u6211\u4eecj\u4ece\u5927\u5230\u5c0f\u5faa\u73af\u65f6\uff0c\u4e5f\u4e0d\u4f1a\u7528\u5230dp[i][j……]\u4e4b\u540e\u7684\u6570\u636e<\/p>\n\n\n\n
    \u6240\u4ee5\u6211\u4eec\u53ef\u4ee5\u53bb\u6389\u4e00\u7ef4\uff1a<\/p>\n\n\n\n
    dp[i]=max(dp[i],dp[j-w[i]]);\/\/j>=w[i]\u65f6<\/code><\/pre>\n\n\n\n
    \u5f53\u6211\u4eec\u5faa\u73af\u5230dp[i]\u65f6,\u53ea\u8981\u8fd8\u6ca1\u6267\u884c\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\uff0c\u90a3\u4e48\u5f53\u524d\u7684dp[i]\u53ca(dp[……i])\u4e4b\u524d\u7684\u6570\u636e\u90fd\u662fi-1\u4ef6\u7269\u54c1\u65f6\u7684\u6570\u636e;\u4ee3\u7801\u4e5f\u5c31\u53d8\u6210\u4e86\u8fd9\u6837\uff1a<\/p>\n\n\n\n
    for (int i = 1; i <= N; i++)\r\n{\r\n\tfor (int j = W; j >= 0; j--)\r\n\t{\r\n\t\tif (j >= w[i])\r\n\t\t{\r\n\t\t\tdp[i]=max(dp[i],dp[j-w[i]]);\r\n\t\t}\r\n\t\telse\r\n\t\t{\r\n\t\t\tdp[j] = dp[j];\r\n\t\t}\r\n\t}\r\n}\r\n\/\/\u5b8c\u5168\u7b49\u4ef7\u4e8e\u4e8c\u7ef4\u7684<\/code><\/pre>\n\n\n\n
    \u5f88\u660e\u663e\uff0cdp[j]==dp[j]\u663e\u7136\u662f\u6ca1\u6709\u610f\u4e49\u7684\uff0c\u5e76\u4e14w[i]>0;\u6240\u4ee5\u4ee3\u7801\u4f18\u5316\u6210\u4e0b\u9762\u7684\u6837\u5b50\uff1a<\/p>\n\n\n\n
    for (int i = 1; i <= N; i++)\n{\n\tfor (int j = W; j >= w[i]; j--)\n\t{\n\t\tdp[j]=max(dp[j],dp[j-w[i]]);\n\t}\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
    \u9898\u76ee \u6700\u57fa\u672c\u7684\u80cc\u5305\u95ee\u9898\u5c31\u662f01\u80cc\u5305\u95ee\u9898\uff0801 knapsack problem\uff09\uff1a\u4e00\u5171\u6709N\u4ef6\u7269\u54c1\uff0c\u7b2ci\uff08i\u4ece1 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12,20],"tags":[19],"class_list":["post-603","post","type-post","status-publish","format-standard","hentry","category-c-c","category-20","tag-19"],"_links":{"self":[{"href":"https:\/\/lolife.top\/index.php?rest_route=\/wp\/v2\/posts\/603","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lolife.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lolife.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lolife.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/lolife.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=603"}],"version-history":[{"count":1,"href":"https:\/\/lolife.top\/index.php?rest_route=\/wp\/v2\/posts\/603\/revisions"}],"predecessor-version":[{"id":604,"href":"https:\/\/lolife.top\/index.php?rest_route=\/wp\/v2\/posts\/603\/revisions\/604"}],"wp:attachment":[{"href":"https:\/\/lolife.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=603"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lolife.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=603"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lolife.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=603"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}