{"id":62,"date":"2011-10-30T02:23:31","date_gmt":"2011-10-29T18:23:31","guid":{"rendered":"http:\/\/rexdf.website.org\/?p=4"},"modified":"2011-10-30T02:23:31","modified_gmt":"2011-10-29T18:23:31","slug":"poj1014-%e5%a4%9a%e9%87%8d%e8%83%8c%e5%8c%85-%e4%ba%8c%e8%bf%9b%e5%88%b6%e4%bc%98%e5%8c%96-%e5%8f%96%e6%a8%a1%e4%bc%98%e5%8c%96","status":"publish","type":"post","link":"https:\/\/blog.rexdf.org\/ja\/2011\/10\/poj1014-%e5%a4%9a%e9%87%8d%e8%83%8c%e5%8c%85-%e4%ba%8c%e8%bf%9b%e5%88%b6%e4%bc%98%e5%8c%96-%e5%8f%96%e6%a8%a1%e4%bc%98%e5%8c%96\/","title":{"rendered":"POJ1014: \u591a\u91cd\u80cc\u5305 + \u4e8c\u8fdb\u5236\u4f18\u5316 + \u53d6\u6a21\u4f18\u5316"},"content":{"rendered":"

 <\/p>\n

\u95ee\u9898\u63cf\u8ff0\uff1a<\/p>\n

\u6709\u82e5\u5e72\u4ef7\u503c\u4e3a\u5206\u522b\u4e3a1\uff0c2 \uff0c3\uff0c4\uff0c5\uff0c6\u7684\u5927\u7406\u77f3\uff0c\u6c42\u603b\u4ef7\u503c\u7684\u5747\u5206\u7b56\u7565\u3002\u8bbe\u4ef7\u503c\u4e3aV\u7684\u77f3\u5934\u91cd\u91cf\u4e3aV,\u8fd9\u6279\u77f3\u5934\u7684\u603b\u4ef7\u503c\u4e3aSUM,\u5219\u95ee\u9898\u8f6c\u5316\u4e3a\u9009\u53d6\u82e5\u5e72\u5927\u7406\u77f3\u5c06\u5bb9\u91cf\u4e3aSUM\/2\u7684\u80cc\u5305\u88c5\u6ee1\u3002<\/p>\n

\u80cc\u5305\u95ee\u9898\uff08\u53c2\u8003\u201c\u80cc\u5305\u95ee\u98989\u8bb2\u201d\uff09<\/p>\n

\u6709N\u4ef6\u7269\u54c1\u548c\u4e00\u4e2a\u5bb9\u91cf\u4e3aV\u7684\u80cc\u5305\uff0c\u7b2ci\u4ef6\u7269\u54c1\u7684\u8d39\u7528\u662fc[i]\uff0c\u4ef7\u503c\u662fw[i]\u3002 f[i][v]\u8868\u793a\u524di\u4ef6\u7269\u54c1\u6070\u653e\u5165\u4e00\u4e2a\u5bb9\u91cf\u4e3av\u7684\u80cc\u5305\u53ef\u4ee5\u83b7\u5f97\u7684\u6700\u5927\u4ef7\u503c,\u5219\u6709\uff1a<\/p>\n

0-1\u80cc\u5305<\/p>\n

\n\n\n\n\n\n\n
\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b<\/td>\nf[i][v] = max{f[i-1][v], f[i-1][v-c[i]]+w[i]}<\/td>\n<\/tr>\n
\u89e3\u6cd5 O(VN)<\/td>\nfor i = 1\u2026N<\/p>\n

for v = V\u2026c[i]<\/p>\n

f[v] = max{f[v], f[v-c[i]]+w[i]};<\/td>\n<\/tr>\n

\u5b50\u8fc7\u7a0b<\/td>\nprocedure ZeroOnePack(cost, weight)<\/p>\n

for v = V\u2026cost<\/p>\n

f[v] = max{f[v], f[v-cost]+weight}<\/td>\n<\/tr>\n

\u521d\u59cb\u5316<\/td>\n\u8981\u6c42\u6070\u597d\u88c5\u6ee1\u80cc\u5305\uff1a f[0] = 0, f[1\u2026V] = \u20131<\/p>\n

\u53ea\u8981\u6c42\u4ef7\u503c\u6700\u5927: f[0\u2026V] = 0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n

\u5b8c\u5168\u80cc\u5305<\/p>\n

\n\n\n\n\n\n
\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b O(V*\u03a3(V\/c[i]))<\/td>\nf[i][v] = max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}<\/td>\n<\/tr>\n
\u8f6c\u5316\u4e3a0-1\u80cc\u5305\u95ee\u9898 O(VN)<\/td>\nfor i = 1\u2026N<\/p>\n

for v = cost\u2026V<\/p>\n

f[v] = max{f[v], f[v-cost]+weight}<\/td>\n<\/tr>\n

\u5b50\u8fc7\u7a0b<\/td>\nprocedure CompletePack(cost, weight)<\/p>\n

for v = cost\u2026V<\/p>\n

f[v] = max{f[v], f[v-cost]+weight}<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n

\u591a\u91cd\u80cc\u5305 (\u6307\u5b9a\u6bcf\u4ef6\u7269\u54c1\u7684\u4e2a\u6570n[i])<\/p>\n

\n\n\n\n\n\n
\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b O(V*\u03a3n[i])<\/td>\nf[i][v] = max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}<\/td>\n<\/tr>\n
\u4e8c\u8fdb\u5236\u4f18\u5316 O(V*\u03a3log(n[i]))<\/td>\n\u5c06\u7b2ci\u79cd\u7269\u54c1\u4ee52\u7684\u6307\u6570\u5206\u5806\uff1a1\uff0c2\uff0c4\uff0c\u2026\uff0c2^(k-1)\uff0cn[i]-2^k+1,\u4e14<\/p>\n

k\u662f\u6ee1\u8db3n[i]-2^k+1>0\u7684\u6700\u5927\u6574\u6570\u3002\u6bcf\u6b21\u5904\u7406\u4e00\u5806\u800c\u4e0d\u662f\u4e00\u4e2a\u7269\u54c1\u3002<\/td>\n<\/tr>\n

\u4f2a\u4ee3\u7801<\/td>\nprocedure MultiplePack(cost, weight, amount)<\/p>\n

if cost*amount>=V<\/p>\n

CompletePack(cost, weight)<\/p>\n

return<\/p>\n

integer k=1<\/p>\n

while k<amount<\/p>\n

ZeroOnePack(k*cost, k*weight)<\/p>\n

amount = amount \u2013 k<\/p>\n

k = k * 2<\/p>\n

ZeroOnePack(amount*cost, amount*weight)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n

\u53d6\u6a21\u4f18\u5316<\/p>\n

\u5f53\u8f93\u5165\u6837\u672c\u7279\u522b\u5927\u65f6\uff0c\u6bd4\u5982\u7ed9\u51fa\u4e0a\u767e\u4e07\u4ef6\u7269\u54c1\uff0c\u8fd9\u65f6\u5019\u4ec5\u9760\u4f18\u5316\u7b97\u6cd5\u4ecd\u7136\u4e0d\u80fd\u4f7f\u8fd0\u884c\u65f6\u95f4\u964d\u5230\u6ee1\u610f\u7684\u8303\u56f4\u3002\u53ef\u8003\u8651\u5982\u4f55\u51cf\u5c11\u8f93\u5165\u6837\u672c\u3002poj1014\u7684discussion\u4e0a\u6709\u4e00\u4e2a\u975e\u5e38\u5de7\u5999\u7684\u201c\u53d6\u6a21\u4f18\u5316\u201d\u6cd5\u3002<\/p>\n

\u8bbe\u4ef7\u503c\u4e3av(1<=v<=6)\u7684\u7269\u54c1\u5171\u6709n\u4ef6\uff0c\u6211\u4eec\u5e0c\u671b\u627e\u5230\u4e00\u4e2a\u6bd4\u8f83\u5c0f\u7684\u6570s(s<n), \u4e14\u5c06n\u4ef6\u7269\u54c1v\u51cf\u5c11\u5230s\u6216s-1\u4ef6\uff0c\u95ee\u9898\u7684\u53ef\u5206\u6027\u4e0d\u53d8\u3002\u8003\u8651\u4e0d\u53ef\u5206\u548c\u53ef\u5206\u4e24\u79cd\u60c5\u51b5\uff1a<\/p>\n