{"id":51,"date":"2022-11-03T19:50:51","date_gmt":"2022-11-03T11:50:51","guid":{"rendered":"https:\/\/blog.myownweb.vip\/?p=51"},"modified":"2022-11-06T22:50:53","modified_gmt":"2022-11-06T14:50:53","slug":"dp-bag","status":"publish","type":"post","link":"https:\/\/forelink.top\/index.php\/2022\/11\/03\/dp-bag\/","title":{"rendered":"\u52a8\u6001\u89c4\u5212-\u80cc\u5305\u95ee\u9898\uff0801\uff0c\u591a\u91cd\uff0c\u5b8c\u5168\uff09"},"content":{"rendered":"\n

01\u80cc\u5305<\/strong>\u2014\u2014>\u62ff\u6216\u4e0d\u62ff\u7684\u95ee\u9898\u3002<\/strong><\/h2>\n\n\n\n

\u95ee\u9898\uff1a\u6709N\u4ef6\u4f53\u79ef\u4e3av\uff0c\u4ef7\u503c\u4e3aw\u7684\u7269\u54c1\u3002\u548c\u4e00\u4e2a\u4f53\u79ef\u4e3aV\u7684\u80cc\u5305\uff0c\u6c42\u89e3\u5c06\u54ea\u4e9b\u7269\u54c1\u88c5\u5165\u80cc\u5305\uff0c\u53ef\u4f7f\u8fd9\u4e9b\u7269\u54c1\u7684\u603b\u4f53\u79ef\u4e0d\u8d85\u8fc7\u80cc\u5305\u5bb9\u91cf\uff0c\u4e14\u603b\u4ef7\u503c\u6700\u5927\u3002
\u8f93\u51fa\u6700\u5927\u4ef7\u503c\u3002<\/strong><\/p>\n\n\n\n

\u53ef\u4ee5\u5148\u5b9a\u4e49\u4e00\u4e2a\u4e8c\u7ef4\u6570\u7ec4dp[i][j]\u8868\u793a\u5728\u7b2ci\u4ef6\u7269\u54c1\uff0c\u4f53\u79ef\u4e3aj\u7684\u65f6\u5019\u7684\u603b\u4ef7\u503c\u3002
\u53ef\u4ee5\u63a8\u51fa\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\uff1a<\/strong><\/p>\n\n\n\n

dp[i][j]=max ( dp[i-1][j] , dp[i-1][j-v[i]]+w[i]<\/strong>\uff09<\/p>\n\n\n\n

\u7531\u6b64\u53ef\u77e5\u7528\u53cc\u91cd\u5faa\u73af\u904d\u5386\u6240\u6709\u7269\u54c1\u548c\u4f53\u79ef\uff0c\u53ef\u4ee5\u63a8\u51fa\u7b54\u6848\u5373dp[N][V]\u7684\u503c\u3002
\u4ee3\u7801\u5982\u4e0b\u3002<\/strong><\/p>\n\n\n\n

\/\/01\u80cc\u5305\u95ee\u9898\u3002\n#include <iostream>\nusing namespace std;\nint N,V;\/\/N\u4ef6\u7269\u54c1\uff0cV\u4e3a\u80cc\u5305\u5bb9\u91cf\u3002\nint v[1005],w[1005];\/\/v\u4e3a\u7269\u54c1\u7684\u4f53\u79ef\uff0cw\u4e3a\u7269\u54c1\u7684\u4ef7\u503c\u3002\nint dp[1005][1005];\/\/dp[i][j]\u4e3a\u4ef7\u503c\u91cf i\u4e3a\u7b2ci\u4ef6\u7269\u54c1\uff0cj\u4e3a\u80cc\u5305\u5269\u4f59\u7684\u5bb9\u91cf\u3002\n\/\/\uff01\uff01dp[0][0-1005]\u4e3a0\uff08\u6709\u53ef\u80fd\u4f1a\u6709\u6d4b\u8bd5\u70b9\u6d4b0,0\uff09\nint main(){\n\tcin>>N>>V;\n\t\/\/\u5b58\u50a8\u6570\u636e\u3002\n\tfor(int i=1;i<=N;i++){\n\t\tcin>>v[i]>>w[i];\n\t}\n\t\/\/\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\uff1a\n\tfor(int i=1;i<=N;i++){\n\t\tfor(int k=1;k<=V;k++){\n\t\t\tif(k<v[i])\/\/\u5982\u679c\u7b2ci\u4e2a\u7269\u54c1\u653e\u4e0d\u4e0b\u3002\n\t\t\t\tdp[i][k]=dp[i-1][k];\/\/\u8fd9\u4e2a\u7269\u54c1\u4e0d\u62ff\u3002\n\t\t\telse\n\t\t\t\tdp[i][k]=max(dp[i-1][k],dp[i-1][k-v[i]]+w[i]);\/\/\u4e0d\u62ff\u6216\u62ff\u3002\n\t\t}\n\t}\n\tcout<<dp[N][V];\/\/\u8f93\u51fa\u7b54\u6848\u3002\n}<\/code><\/pre>\n\n\n\n
\u4f46\u662f\u53ef\u4ee5\u53d1\u73b0\u8fd0\u7528\u4e8c\u7ef4\u6570\u7ec4\u8bb0\u5f55\u7b54\u6848\u5373\u6d6a\u8d39\u7a7a\u95f4\u4e5f\u6d6a\u8d39\u65f6\u95f4\uff0c\u670910000\u4ef6\u4ee5\u4e0a\u7269\u54c1\u7684\u65f6\u5019\u5f88\u5bb9\u6613\u8d85\u65f6\u3002
\u6240\u4ee5\u53ef\u4ee5\u628adp\u4e8c\u7ef4\u6570\u7ec4\u538b\u7f29\u6210\u4e00\u7ef4\u6570\u7ec4\u4f18\u5316\uff0c\u5373\u6eda\u52a8\u6570\u7ec4\u4f18\u5316\u3002<\/strong><\/p>\n\n\n\n
\u6253\u8868\u53ef\u4ee5\u53d1\u73b0\uff0c\u5728\u9012\u63a8\u7684\u8fc7\u7a0b\u4e2d\u53ea\u662f\u7528\u5230\u4e86\u548c\u4e0a\u4e00\u5c42\u7684\u6570\u636e\u3002<\/strong><\/p>\n\n\n\n
\"\"<\/div>
\u5982\u56fe\u4e2d\u7684\u6570\u5b575\u662f\u901a\u8fc7\u4e0a\u9762\u7684\u6570\u636e\u63a8\u51fa\u6765\u7684\u3002<\/figcaption><\/figure>\n\n\n\n
\u6240\u4ee5\u53ef\u4ee5\u6570\u7ec4\u4e0b\u6807\u53ea\u8bb0\u5f55\u80cc\u5305\u7684\u4f53\u79ef dp[V]\uff0c\u5e76\u901a\u8fc7\u4e0d\u65ad\u7684\u8986\u76d6\u907f\u514d\u4e86\u8bb0\u5f55\u5927\u91cf\u65e0\u7528\u6570\u636e\u7684\u95ee\u9898\u3002\uff08\uff1f\uff09<\/strong>
           <\/p>\n\n\n\n
\uff08\u5751\u70b9\uff09\u4f46\u662f\u8981\u6ce8\u610f\u7684\u662f\uff0c\u7528\u4e00\u7ef4\u6570\u7ec4\u6eda\u52a8\u8981\u907f\u514d\u53ef\u80fd\u8981\u7528\u7684\u6570\u636e\u8fc7\u65e9\u88ab\u8986\u76d6\u7684\u95ee\u9898\uff0c\u8868\u4e2d\u6b63\u5411\u4f53\u79efV\u662f\u4e0d\u65ad\u589e\u5927\u7684\uff0c\u5c0f\u80cc\u5305\u80fd\u88c5\u7684\u4e1c\u897f\u5927\u80cc\u5305\u4e5f\u4e00\u5b9a\u80fd\u88c5\uff0c\u53cd\u8fc7\u6765\u5c31\u4e0d\u4e00\u5b9a\u4e86\uff0c\u6240\u4ee5\u8981\u9006\u5411\u53bb\u66f4\u65b0\u8986\u76d6\u6570\u7ec4\u4e2d\u7684\u6570\u636e\u3002<\/strong><\/p>\n\n\n\n
\u4ee3\u7801\u5982\u4e0b\u3002<\/strong><\/p>\n\n\n\n
\/\/01\u80cc\u5305\u95ee\u9898\u3002\n#include <iostream>\nusing namespace std;\nint N,V;\/\/N\u4ef6\u7269\u54c1\uff0cV\u4e3a\u80cc\u5305\u5bb9\u91cf\u3002\nint v[1005],w[1005];\/\/v\u4e3a\u7269\u54c1\u7684\u4f53\u79ef\uff0cw\u4e3a\u7269\u54c1\u7684\u4ef7\u503c\u3002\nint dp[1005];\/\/dp[j]\u4e3a\u4f53\u79ef\u4e3aJ\u65f6\u80fd\u88c5\u7684\u4ef7\u503c\u91cf\u3002 j\u4e3a\u80cc\u5305\u5269\u4f59\u7684\u5bb9\u91cf\u3002\n\/\/\uff01\uff01dp[0][0-1005]\u4e3a0\uff08\u6709\u53ef\u80fd\u4f1a\u6709\u6d4b\u8bd5\u70b9\u6d4b0,0\uff09\nint main(){\n\tcin>>N>>V;\n\t\/\/\u5b58\u50a8\u6570\u636e\u3002\n\tfor(int i=1;i<=N;i++){\n\t\tcin>>v[i]>>w[i];\n\t}\n\t\/\/\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\uff1a\n\tfor(int i=1;i<=N;i++){\n\t\tfor(int k=1;k<=V;k++){\n\t\t\tif(k<v[i])\/\/\u5982\u679c\u7b2ci\u4e2a\u7269\u54c1\u653e\u4e0d\u4e0b\u3002\n\t\t\t\tdp[i][k]=dp[i-1][k];\/\/\u8fd9\u4e2a\u7269\u54c1\u4e0d\u62ff\u3002\n\t\t\telse\n\t\t\t\tdp[i][k]=max(dp[i-1][k],dp[i-1][k-v[i]]+w[i]);\/\/\u4e0d\u62ff\u6216\u62ff\u3002\n\t\t}\n\t}\n\tcout<<dp[N][V];\/\/\u8f93\u51fa\u7b54\u6848\u3002\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
\u5b8c\u5168\u80cc\u5305\u95ee\u9898\uff08\u6bcf\u4ef6\u7269\u54c1\u90fd\u6709\u65e0\u9650\u4ef6\uff09<\/h2>\n\n\n\n
\u95ee\u9898\uff1a\u6709N\u79cd\u4f53\u79ef\u4e3av\uff0c\u4ef7\u503c\u4e3aw\u7684\u7269\u54c1\u3002\u548c\u4e00\u4e2a\u4f53\u79ef\u4e3aV\u7684\u80cc\u5305\uff0c\u6bcf\u79cd\u7269\u54c1\u7684\u6570\u91cf\u662f\u65e0\u9650\u7684\uff0c\u6c42\u89e3\u5c06\u600e\u6837\u5c06\u7269\u54c1\u5206\u914d\u5165\u80cc\u5305\uff0c\u53ef\u4f7f\u8fd9\u4e9b\u7269\u54c1\u7684\u603b\u4f53\u79ef\u4e0d\u8d85\u8fc7\u80cc\u5305\u5bb9\u91cf\uff0c\u4e14\u603b\u4ef7\u503c\u6700\u5927\u3002
\u8f93\u51fa\u6700\u5927\u4ef7\u503c\u3002<\/strong><\/p>\n\n\n\n
\u56e0\u4e3a\u7269\u54c1\u65e0\u9650\u6240\u4ee5\u53ef\u4ee5\u53d8\u62100\/1\/2\/3…\u80cc\u5305\u95ee\u9898\uff08\uff1f\uff09<\/strong><\/p>\n\n\n\n
\u8bf6\u563f\uff0c\u8bbek\u4e3a\u53d6\u7528\u4e00\u79cd\u7269\u54c1\u7684\u6570\u91cf\uff0c\u89c2\u5bdf\u539f\u6765\u7684\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\uff0c\u53d1\u73b0\u53ef\u4ee5\u5728\u539f\u6765\u7684\u57fa\u7840\u4e0a\u505a\u4e00\u4e9b\u5c0f\u66f4\u6539\u3002<\/strong>
dp[i][j]=max ( dp[i-1][j] , dp[i-1][j-v[i]]+w[i]<\/strong>\uff09
\u2193\u2193\u2193                                                              \u2193\u2193\u2193<\/strong>
dp[i][j]=max ( dp[i-1][j] , dp[i-1][j-k*v[i]]+k*w[i]<\/strong>\uff09
\u518d\u7528\u6eda\u52a8\u6570\u7ec4\u4f18\u5316<\/strong>
dp[j]=max ( dp[j] , dp[j-k*v[i]]+k*w[i]<\/strong>\uff09<\/p>\n\n\n\n
\u4ee3\u7801\u5982\u4e0b\uff1a<\/strong><\/p>\n\n\n\n
#include <iostream>\nusing namespace std;\nint w[1005],v[1005],dp[1005];\nint main(){\n\tint N,V; cin>>N>>V;\/\/N\u4e3a\u7269\u54c1\u6570\u91cf\uff0cV\u4e3a\u80cc\u5305\u4f53\u79ef\u3002\n\tfor(int i=1;i<=N;i++)\n\tcin>>v[i]>>w[i];\n\tfor(int i=1;i<=N;i++){\n\t\tfor(int j = V;j>=0;k++){\n\t\t\tfor(int k=0;k<=j\/v[i];k++)\n\t\t\tdp[j] = max(dp[j],dp[j-k*v[i]]+k*w[i]);\/\/\u4e0d\u7528\u5224\u65ad\u80fd\u4e0d\u80fd\u88c5\u5f97\u4e0b\u4e86\u3002\n\t\t}\n\t}\n\tcout<<dp[V];\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\u4f46\u662f\u56e0\u4e3a\u7528\u5230\u4e86\u4e09\u91cd\u5faa\u73af\uff0c\u6240\u4ee5\u8fd9\u662f\u975e\u5e38\u571f\u7684\u65b9\u6cd5\u3002<\/strong><\/p>\n\n\n\n
\u53ef\u4ee5\u518d\u6253\u4e2a\u8868\u770b\u770b\u3002<\/strong><\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u53ef\u4ee5\u53d1\u73b0\u65b0\u7684\u6570\u636e\u662f\u6765\u81ea\u4e8e\u4e0a\u4e00\u884c\u6570\u636e\u548c\u65b0\u4ea7\u751f\u7684\u6570\u636e\u3002
\u572801\u80cc\u5305\u7684\u6eda\u52a8\u6570\u7ec4\u91cc\uff0c\u65b0\u7684\u6570\u636e\u662f\u6765\u81ea\u4e8e\u4e0a\u4e00\u884c\u548c\u4e0a\u4e00\u884c\u7684\u65e7\u6570\u636e\u5f97\u51fa\u7684\u3002
\u6240\u4ee5\u5728\u5b8c\u5168\u80cc\u5305\u53ef\u4ee5\u65e0\u9700\u7ed9\u53d6\u7528\u7684\u7269\u54c1\u8ba1\u6570\uff0c\u76f4\u5230\u62ff\u4e0d\u4e0b\u4e3a\u6b62\uff0c\u4ece0\u5f00\u59cb\uff0c\u987a\u5411\u53bb\u6c42\u89e3dp[V]\u7684\u503c\u3002<\/strong><\/p>\n\n\n\n
\u4ee3\u7801\u5982\u4e0b\u3002<\/strong><\/p>\n\n\n\n
#include <iostream>\nusing namespace std;\nint w[1005],v[1005],dp[1005];\nint main(){\n\tint N,V; cin>>N>>V;\/\/N\u4e3a\u7269\u54c1\u6570\u91cf\uff0cV\u4e3a\u80cc\u5305\u4f53\u79ef\u3002\n\tfor(int i=1;i<=N;i++)\n\tcin>>v[i]>>w[i];\n\tfor(int i=1;i<=N;i++){\n\t\tfor(int k = 1;k<=V;k++){\/\/\u987a\u5411<\/strong>\uff0c\u8981\u7528\u5230\u65b0\u6570\u636e\u3002\n\t\t\tif(k>=v[i])\/\/\u53ef\u4ee5\u4ecev[i]\u5f00\u59cb\u7701\u6389\u4e00\u6b21\u5224\u65ad\uff08\u4f18\u5316\u3002\n\t\t\tdp[k] = max(dp[k],dp[k-v[i]]+w[i]);\n\t\t}\n\t}\n\tcout<<dp[V];\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\u975e\u5e38\u7684\u5947\u5999\u3002<\/strong><\/p>\n\n\n\n
\n\n\n\n
\u591a\u91cd\u80cc\u5305\u95ee\u9898\uff08\u8981\u53d8\u621001\u80cc\u5305\u95ee\u9898\u5417\uff1f\uff09<\/h2>\n\n\n\n
\u76f4\u63a5\u62c6\u621001\u80cc\u5305\u95ee\u9898\u662f\u53ef\u4ee5\u7684\uff0c\u4e5f\u53ef\u4ee5\u591a\u52a0\u4e00\u5c42\u5faa\u73af\u3002<\/strong><\/p>\n\n\n\n
for(int l=0;l<=s[i]&&l*v[i]<=k;l++)<\/strong><\/p>\n\n\n\n
\u8fd8\u6709\u611f\u89c9\u975e\u5e38\u5e05\u6c14\uff0c\u77ed\u5c0f\u7cbe\u608d\u7684saber\u7b80\u5316\u4ee3\u7801\u3002<\/strong><\/p>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nint dp[1005],n,t,v,w,s;\nmain()\n{\n    cin>>n>>t;\n    while(n--)\n    {\n    cin>>w>>v>>s;\n    while(s--)\n    for(int j=t;j>=w;j--)\n    dp[j]=max(dp[j],dp[j-w]+v);\n    }\n    cout<<dp[t];\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
\u4e8c\u7ef4\u8d39\u7528\u80cc\u5305\u95ee\u9898\uff08\u6709\u5751\u70b9\uff09\uff08\u5f85\u7eed\uff09<\/h2>\n","protected":false},"excerpt":{"rendered":"
01\u80cc\u5305\u2014\u2014>\u62ff\u6216\u4e0d\u62ff\u7684\u95ee\u9898\u3002 \u95ee\u9898\uff1a\u6709N\u4ef6\u4f53\u79ef\u4e3av\uff0c\u4ef7\u503c\u4e3aw\u7684\u7269\u54c1\u3002\u548c\u4e00\u4e2a\u4f53\u79ef\u4e3aV\u7684\u80cc\u5305\uff0c\u6c42\u89e3\u5c06\u54ea\u4e9b\u7269 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[8],"tags":[],"class_list":["post-51","post","type-post","status-publish","format-standard","hentry","category-8"],"_links":{"self":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/51","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/comments?post=51"}],"version-history":[{"count":7,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/51\/revisions"}],"predecessor-version":[{"id":77,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/51\/revisions\/77"}],"wp:attachment":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/media?parent=51"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/categories?post=51"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/tags?post=51"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}