{"id":2598,"date":"2019-12-30T15:58:07","date_gmt":"2019-12-30T07:58:07","guid":{"rendered":"http:\/\/www.sniper97.cn\/?p=2598"},"modified":"2019-12-30T15:58:07","modified_gmt":"2019-12-30T07:58:07","slug":"%e3%80%90%e7%ae%97%e6%b3%95%e5%88%86%e6%9e%90%e4%b8%8e%e8%ae%be%e8%ae%a1%e3%80%91%e8%b4%aa%e5%bf%83%e7%ae%97%e6%b3%95","status":"publish","type":"post","link":"http:\/\/www.sniper97.cn\/index.php\/note\/introduction_to_algorithms\/2598\/","title":{"rendered":"\u3010\u7b97\u6cd5\u5bfc\u8bba\u3011\u8d2a\u5fc3\u7b97\u6cd5"},"content":{"rendered":"\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" width=\"303\" height=\"241\" src=\"\/wp-content\/uploads\/2019\/12\/\u56fe\u7247-40.png\" alt=\"\" class=\"wp-image-2607\" srcset=\"http:\/\/www.sniper97.cn\/wp-content\/uploads\/2019\/12\/\u56fe\u7247-40.png 303w, http:\/\/www.sniper97.cn\/wp-content\/uploads\/2019\/12\/\u56fe\u7247-40-300x239.png 300w\" sizes=\"(max-width: 303px) 100vw, 303px\" \/><\/figure><\/div>\n\n\n<p>\u6c42\u89e3\u6700\u4f18\u5316\u95ee\u9898\u7684\u7b97\u6cd5\u901a\u5e38\u9700\u8981\u7ecf\u8fc7\u4e00\u7cfb\u5217\u7684\u6b65\u9aa4\uff0c\u5728\u6bcf\u4e2a\u6b65\u9aa4\u90fd\u9762\u4e34\u591a\u79cd\u9009\u62e9\u3002\u5bf9\u4e8e\u8bb8\u591a\u6700\u4f18\u5316\u95ee\u9898\uff0c\u4f7f\u7528\u52a8\u6001\u89c4\u5212\u7b97\u6cd5\u6765\u6c42\u89e3\u6700\u4f18\u89e3\u95ee\u9898\u6709\u4e9b\u6740\u9e21\u7528\u725b\u5200\u4e86\uff0c\u53ef\u4ee5\u4f7f\u7528\u66f4\u7b80\u5355\u3001\u66f4\u9ad8\u6548\u7684\u7b97\u6cd5\uff0c\u4e5f\u5c31\u662f<strong>\u8d2a\u5fc3\u7b97\u6cd5<\/strong>\u6765\u89e3\u51b3\u8fd9\u4e00\u95ee\u9898\u3002<\/p>\n\n\n<p>\u9700\u8981\u4e3b\u4e49\uff0c\u8d2a\u5fc3\u7b97\u6cd5\u5e76\u4e0d\u4fdd\u8bc1\u5f97\u5230\u7684\u662f\u6700\u4f18\u89e3\uff0c\u4f46\u662f\u5bf9\u4e8e\u5f88\u591a\u95ee\u9898\u786e\u5b9e\u53ef\u4ee5\u5f97\u5230\u6700\u4f18\u89e3\u3002<\/p>\n\n\n<h2 class=\"wp-block-heading\">1.\u6d3b\u52a8\u9009\u62e9\u95ee\u9898<\/h2>\n\n\n<p>\u7b2c\u4e00\u4e2a\u4f8b\u5b50\u662f\u8c03\u5ea6\u7ade\u4e89\u5171\u4eab\u8d44\u6e90\u7684\u95ee\u9898\uff0c\u76ee\u6807\u662f\u9009\u51fa\u4e00\u4e2a\u6700\u5927\u7684\u4e92\u76f8\u517c\u5bb9\u7684\u6d3b\u52a8\u96c6\u5408\u3002<\/p>\n\n\n<p>\u5047\u8bbe\u6709\u51e0\u4e2an\u4e2a\u957f\u5ea6\u7684\u96c6\u5408S\uff0c\u8fd9\u4e9b\u6d3b\u52a8\u5360\u7528\u4e00\u4e2a\u5171\u540c\u7684\u8d44\u6e90\uff0c\u5305\u62ec\u4e00\u4e2a\u5f00\u59cb\u65f6\u95f4\u548c\u7ed3\u675f\u65f6\u95f4\uff0c\u6211\u4eec\u9700\u8981\u9009\u53d6\u4e00\u4e2a\u80fd\u591f\u63a5\u7eb3\u6700\u591a\u6d3b\u52a8\u7684\u5e8f\u5217\u96c6\u5408\u3002<\/p>\n\n\n<h3 class=\"wp-block-heading\">1.\u52a8\u6001\u89c4\u5212\u89e3\u51b3\u6d3b\u52a8\u9009\u62e9\u95ee\u9898<\/h3>\n\n\n<p>\u5bf9\u4e8e\u4f7f\u7528\u52a8\u6001\u89c4\u5212\u89e3\u51b3\u8fd9\u7c7b\u95ee\u9898\uff0c\u663e\u800c\u6613\u89c1\u7684 \u6700\u4f18\u5b50\u7ed3\u6784\u662fi~j\u65f6\u95f4\u5185\u7684\u6700\u4f18\u89e3\u3002<\/p>\n\n\n<p>\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n\n\n<pre class=\"wp-block-preformatted\">def choose_best_activity_with_dp(self, S, i, j):<br \/>    <em>\"\"\"<br \/><\/em><em>    <\/em><em>\u4f7f\u7528\u52a8\u6001\u89c4\u5212\u8ba1\u7b97\u6700\u4f73\u6d3b\u52a8\u9009\u62e9<br \/><\/em><em>    <\/em><strong><em>:param<\/em><\/strong><em> S: <\/em><em>\u6d3b\u52a8\u5217\u8868<br \/><\/em><em>    <\/em><strong><em>:param<\/em><\/strong><em> i: <\/em><em>\u8d77\u59cb\u65f6\u95f4<br \/><\/em><em>    <\/em><strong><em>:param<\/em><\/strong><em> j: <\/em><em>\u7ec8\u6b62\u65f6\u95f4<br \/><\/em><em>    <\/em><strong><em>:return<\/em><\/strong><em>:<br \/><\/em><em>    \"\"\"<br \/><\/em><em>    <\/em># \u7528\u6765\u4fdd\u5b58\u9700\u8981\u5728\u54ea\u4e2a\u70b9\u5206\u5272<br \/>    value = [0 for _ in range(j - i + 1)]<br \/>    # \u7528\u6765\u4fdd\u5b58\u4ecei\u5230j\u6700\u591a\u6709\u51e0\u4e2a\u6d3b\u52a8<br \/>    count = [[0 for _ in range(j - i + 1)] for _ in range(j - i + 1)]<br \/>    # \u521d\u59cb\u5316\uff0c\u6bcf\u4e2a\u6d3b\u52a8\u7684\u8d77\u59cb\u7ec8\u6b62\u65f6\u95f4\u7f6e\u4e3a1<br \/>    for each in S:<br \/>        count[each[1]][each[2]] = 1<br \/>    # dp<br \/>    for x in range(1, len(value)):<br \/>        for y in range(x):  # \u8fd9\u4e2a\u76f8\u5f53\u4e8e\u4e0a\u9762\u8bf4\u7684k<br \/>            if count[i][y] + count[y][x] &gt; count[i][x]:<br \/>                count[i][x] = count[i][y] + count[y][x]<br \/>                value[x] = y<br \/>    return value<\/pre>\n\n\n<h3 class=\"wp-block-heading\">2.\u8d2a\u5fc3\u9009\u62e9\u89e3\u51b3\u6d3b\u52a8\u9009\u62e9\u95ee\u9898<\/h3>\n\n\n<p>\u5982\u679c\u6211\u4eec\u8ba9\u6bcf\u4e00\u9009\u62e9\u6d3b\u52a8\u4e4b\u540e\u5269\u4f59\u8d44\u6e90\u8d8a\u591a\uff0c\u90a3\u4e48\u6211\u4eec\u53ef\u9009\u62e9\u7684\u662f\u4e0d\u662f\u4e5f\u5c31\u8d8a\u591a\u5462\uff0c\u8fd9\u5c31\u662f\u8d2a\u5fc3\u601d\u60f3\uff0c\u5bf9\u4e8e\u8fd9\u9053\u9898\uff0c\u6211\u4eec\u6bcf\u4e00\u6b65\u90fd\u9009\u62e9\u5269\u4f59\u65f6\u95f4\u6700\u591a\u7684\uff0c\u90a3\u4e48\u6211\u4eec\u5c31\u53ef\u4ee5\u9009\u62e9\u5230\u6700\u591a\u7684\u6d3b\u52a8\u3002<\/p>\n\n\n<p>\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n\n\n<pre class=\"wp-block-preformatted\">def greedy_choose(self, S, i, j):<br \/>    <em>\"\"\"<br \/><\/em><em>    <\/em><em>\u8d2a\u5fc3\u7b97\u6cd5\u89e3\u51b3\u6d3b\u52a8\u95ee\u9898<br \/><\/em><em>    <\/em><strong><em>:param<\/em><\/strong><em> S:<br \/><\/em><em>    <\/em><strong><em>:param<\/em><\/strong><em> i:<br \/><\/em><em>    <\/em><strong><em>:param<\/em><\/strong><em> j:<br \/><\/em><em>    <\/em><strong><em>:return<\/em><\/strong><em>:<br \/><\/em><em>    \"\"\"<br \/><\/em><em>    <\/em># \u8fd4\u56de\u70b9\u96c6\u5408<br \/>    return_list = []<br \/><br \/>    def choose_one(i):<br \/>        <em>\"\"\"<br \/><\/em><em>        <\/em><em>\u9009\u62e9\u4e00\u4e2a<\/em><em>i<\/em><em>\u65f6\u95f4\u70b9\u4e4b\u540e\u5f00\u59cb\uff0c\u5e76\u4e14\u6301\u7eed\u65f6\u95f4\u6700\u77ed\u7684\u6d3b\u52a8<br \/><\/em><em>        <\/em><strong><em>:param<\/em><\/strong><em> i:<br \/><\/em><em>        <\/em><strong><em>:return<\/em><\/strong><em>:<br \/><\/em><em>        \"\"\"<br \/><\/em><em>        <\/em>min_end_time = float('inf')<br \/>        return_one = None<br \/>        for each in S:<br \/>            if each[1] &gt;= i and each[2] &lt; min_end_time:<br \/>                min_end_time = each[2]<br \/>                return_one = each<br \/>        return return_one<br \/><br \/>    x = i<br \/>    while x &lt;= j:<br \/>        one = choose_one(x)<br \/>        if one is None:<br \/>            return return_list<br \/>        return_list.append(one)<br \/>        x = one[2]<\/pre>\n\n\n<h2 class=\"wp-block-heading\">2.\u8d2a\u5fc3\u7b97\u6cd5\u539f\u7406<\/h2>\n\n\n<h3 class=\"wp-block-heading\">1.\u8d2a\u5fc3\u9009\u62e9\u6027\u8d28<\/h3>\n\n\n<p>\u7b2c\u4e00\u4e2a\u5173\u952e\u8981\u7d20\u662f<strong>\u8d2a\u5fc3\u9009\u62e9\u6027\u8d28<\/strong>\uff0c\u6211\u4eec\u53ef\u4ee5\u901a\u8fc7\u505a\u51fa\u5c40\u90e8\u6700\u4f18\uff08\u8d2a\u5fc3\uff09\u9009\u62e9\u6765\u6784\u9020\u51fa\u5168\u5c40\u6700\u4f18\u89e3\u3002\u4e5f\u5c31\u662f\u8bf4\uff0c\u5728\u6bcf\u4e00\u6b65\u6211\u4eec\u90fd\u8003\u8651\u6700\u4f18\u9009\u62e9\uff0c\u800c\u4e0d\u5fc5\u8003\u8651\u5b50\u95ee\u9898\u7684\u89e3\u3002<\/p>\n\n\n<p>\u5728\u52a8\u5f52\u4e2d\uff0c\u6211\u4eec\u6bcf\u4e00\u6b65\u90fd\u8981\u8fdb\u884c\u4e00\u6b21\u9009\u62e9\uff0c\u4f46\u662f\u9009\u62e9\u901a\u5e38\u4f9d\u8d56\u4e8e\u5b50\u95ee\u9898\u7684\u89e3\u3002<\/p>\n\n\n<p>\u5728\u8d2a\u5fc3\u4e2d\uff0c\u6211\u4eec\u603b\u662f\u505a\u51fa\u5f53\u65f6\u770b\u6700\u4f73\u7684\u9009\u62e9\uff0c\u7136\u540e\u6c42\u89e3\u5269\u4e0b\u7684\u552f\u4e00\u7684\u5b50\u95ee\u9898\u3002<\/p>\n\n\n<p>\u603b\u7ed3\u6765\u8bf4\u5c31\u662f\uff0c\u52a8\u5f52\u8981\u6c42\u89e3\u51fa\u6bcf\u4e00\u79cd\u53ef\u80fd\u4e4b\u540e\u624d\u505a\u51fa\u9009\u62e9\uff0c\u800c\u8d2a\u5fc3\u65e9\u65e9\u7684\u5c31\u9009\u62e9\u597d\u4e86\uff0c\u518d\u8ba1\u7b97\u4e0b\u4e00\u6b65\u3002<\/p>\n\n\n<h3 class=\"wp-block-heading\">2.\u8d2a\u5fc3\u5bf9\u52a8\u6001\u89c4\u5212<\/h3>\n\n\n<p>\u7531\u4e8e\u8d2a\u5fc3\u548c\u52a8\u6001\u89c4\u5212\u90fd\u5229\u7528\u4e86\u6700\u4f18\u5b50\u7ed3\u6784\u6027\u8d28\uff0c\u800c\u4e24\u79cd\u65b9\u6cd5\u6709\u4e00\u70b9\u7ec6\u5fae\u5dee\u522b\uff0c\u6211\u4eec\u7814\u7a76\u4e00\u4e2a\u7ecf\u5178\u7684\u6700\u4f18\u5316\u95ee\u9898\u7684\u4e24\u4e2a\u53d8\u5f62\u3002<\/p>\n\n\n<p><strong>0-1\u80cc\u5305\u95ee\u9898<\/strong>\uff1a\u4e00\u4e2a\u5c0f\u5077\u6b63\u5728\u62a2\u52ab\u5546\u5e97\uff0c\u53d1\u73b0\u4e86n\u4ef6\u5546\u54c1\uff0c\u7b2ci\u4e2a\u5546\u54c1\u4ef7\u503cv_i\u5143\uff0c\u91cdw_i\u78c5\u3002\u8fd9\u4e2a\u5c0f\u5077\u5e0c\u671b\u62ff\u8d70\u4ef7\u503c\u5c3d\u91cf\u9ad8\u7684\u5546\u54c1\uff0c\u4f46\u662f\u4ed6\u7684\u80cc\u5305\u6700\u591a\u80fd\u5bb9\u7eb3W\u78c5\u91cd\u7684\u5546\u54c1\u3002\u4ed6\u5e94\u8be5\u62ff\u54ea\u4e9b\u4e1c\u897f\u5462\uff1f<\/p>\n\n\n<p><strong>\u5206\u6570\u80cc\u5305\u95ee\u9898<\/strong>\uff1a\u548c0-1\u80cc\u5305\u7c7b\u4f3c\uff0c\u4e0d\u540c\u7684\u662f\uff0c\u8fd9\u91cc\u5c0f\u5077\u53ef\u4ee5\u9009\u62e9\u62ff\u8d70\u4e00\u90e8\u5206\uff0c\u800c\u4e0d\u662f0-1\u80cc\u5305\u4e2d\u7684\u4e8c\u5143\u9009\u62e9\u95ee\u9898\u3002<\/p>\n\n\n<p>\u53ef\u4ee5\u7406\u89e3\u62100-1\u80cc\u5305\u662f\u91d1\u952d\uff0c\u5206\u6570\u80cc\u5305\u662f\u91d1\u7802\u3002<\/p>\n\n\n<p>\u5bf9\u4e8e\u5206\u6570\u80cc\u5305\u95ee\u9898\uff0c\u6211\u4eec\u53ef\u4ee5\u4f7f\u7528\u8d2a\u5fc3\u7b97\u6cd5\uff0c\u8ba1\u7b97v_i\/w_i\uff0c\u6309\u7167\u4ece\u9ad8\u5230\u4f4e\u62ff\u7269\u54c1\u5373\u53ef\u3002<\/p>\n\n\n<p>\u800c\u5bf9\u4e8e0-1\u80cc\u5305\u95ee\u9898\uff0c\u6211\u4eec\u5c31\u4e0d\u53ef\u4ee5\u8fd9\u4e48\u505a\uff0c\u56e0\u4e3a\u8fd9\u4e48\u62ff\u5f80\u5f80\u53ef\u80fd\u4f1a\u8ba9\u80cc\u5305\u4ea7\u751f\u7a7a\u95f2\uff0c\u4ece\u800c\u964d\u4f4e\u6574\u4f53\u7684\u4ef7\u503c\u3002<\/p>\n\n\n<p>0-1\u80cc\u5305\u4ee3\u7801\uff1a<\/p>\n\n\n<pre class=\"wp-block-preformatted\">def shop_with_dp(self, value, bag_size):<br \/>    <em>\"\"\"<br \/><\/em><em>    0-1<\/em><em>\u80cc\u5305<br \/><\/em><em>    <\/em><strong><em>:param<\/em><\/strong><em> value:<br \/><\/em><em>    <\/em><strong><em>:param<\/em><\/strong><em> bag_size:<br \/><\/em><em>    <\/em><strong><em>:return<\/em><\/strong><em>:<br \/><\/em><em>    \"\"\"<br \/><\/em><em>    <\/em>result = [[0 for _ in range(bag_size+1)] for _ in range(len(value[0]))]<br \/><br \/>    for i in range(0, len(value[0])):<br \/>        for j in range(0, bag_size+1):<br \/>            if value[i][1] &lt;= j:<br \/>                if result[i][j] &lt; result[i-1][j - value[i][1]] + value[i][2]:<br \/>                    result[i][j] = result[i-1][j - value[i][1]] + value[i][2]<br \/>            else:<br \/>                result[i][j] = result[i - 1][j]<br \/>    return result[-1][-1]<\/pre>\n\n\n<p>\u5206\u6570\u80cc\u5305\u4ee3\u7801\uff1a<\/p>\n\n\n<pre class=\"wp-block-preformatted\">def shop_with_greedy_algorithm(self, value, bag_size):<br \/>    <em>\"\"\"<br \/><\/em><em>    <\/em><em>\u5206\u6570\u80cc\u5305\u95ee\u9898<br \/><\/em><em>    <\/em><strong><em>:param<\/em><\/strong><em> value:<br \/><\/em><em>    <\/em><strong><em>:param<\/em><\/strong><em> bag_size:<br \/><\/em><em>    <\/em><strong><em>:return<\/em><\/strong><em>:<br \/><\/em><em>    \"\"\"<br \/><\/em><em>    <\/em>each_value = [0 for _ in range(len(value))]<br \/>    total_value = 0<br \/>    # \u8ba1\u7b97\u5546\u54c1\u5747\u4ef7<br \/>    for i in range(len(each_value)):<br \/>        each_value[i] = value[i][2] \/ value[i][1]<br \/>    # \u5faa\u73af\u88c5\u6ee1\u80cc\u5305<br \/>    while bag_size &gt; 0:<br \/>        most_valued_idx = each_value.index(max(each_value))<br \/>        if value[most_valued_idx][1] &lt; bag_size:<br \/>            # \u5bf9\u5e94\u80cc\u5305\u80fd\u88c5\u6ee1\u5546\u54c1\u7684\u60c5\u51b5<br \/>            bag_size -= value[most_valued_idx][1]<br \/>            total_value += each_value[most_valued_idx] * value[most_valued_idx][1]<br \/>            each_value.remove(each_value[most_valued_idx])<br \/>            value.remove(value[most_valued_idx])<br \/>        else:<br \/>            # \u5bf9\u5e94\u80cc\u5305\u4e0d\u80fd\u88c5\u5168\u90e8\u5546\u54c1\u7684\u60c5\u51b5<br \/>            total_value += bag_size * each_value[most_valued_idx]<br \/>            bag_size = 0<br \/>        pass<br \/>    return total_value<\/pre>\n\n\n<h2 class=\"wp-block-heading\">3.\u54c8\u592b\u66fc\u7f16\u7801<\/h2>\n\n\n<p>\u54c8\u592b\u66fc\u7f16\u7801\u53ef\u4ee5\u5f88\u6709\u6548\u5730\u538b\u7f29\u6570\u636e\uff0c\u901a\u5e38\u53ef\u4ee5\u53ef\u4ee5\u8282\u7ea620~90%\u7a7a\u95f4\u3002<\/p>\n\n\n<p>\u6211\u4eec\u5c06\u5f85\u538b\u7f29\u6570\u636e\u770b\u505a\u5b57\u7b26\u7cfb\u5217\uff0c\u6839\u636e\u6bcf\u4e2a\u5b57\u7b26\u5e8f\u5217\uff0c\u8d2a\u5fc3\u7684\u6784\u9020\u51fa\u5b57\u7b26\u7684\u6700\u4f18\u4e8c\u8fdb\u5236\u8868\u793a\u3002<\/p>\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" width=\"368\" height=\"79\" src=\"\/wp-content\/uploads\/2019\/12\/\u56fe\u7247-38.png\" alt=\"\" class=\"wp-image-2605\" srcset=\"http:\/\/www.sniper97.cn\/wp-content\/uploads\/2019\/12\/\u56fe\u7247-38.png 368w, http:\/\/www.sniper97.cn\/wp-content\/uploads\/2019\/12\/\u56fe\u7247-38-300x64.png 300w\" sizes=\"(max-width: 368px) 100vw, 368px\" \/><\/figure><\/div>\n\n\n<p><strong>\u5b9a\u957f\u7f16\u7801<\/strong>\u53ea\u662f\u6839\u636e\u5b57\u7b26\u51fa\u73b0\u7684\u9891\u7387\u5bf9\u5b57\u7b26\u8fdb\u884c\u4e8c\u8fdb\u5236\u7f16\u53f7\u3002<\/p>\n\n\n<p>\u800c<strong>\u53d8\u957f\u7f16\u7801<\/strong>\uff0c\u753b\u51fa\u5982\u4e0b\u54c8\u5f17\u66fc\u6811<\/p>\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" width=\"510\" height=\"658\" src=\"\/wp-content\/uploads\/2019\/12\/\u56fe\u7247-39.png\" alt=\"\" class=\"wp-image-2606\" srcset=\"http:\/\/www.sniper97.cn\/wp-content\/uploads\/2019\/12\/\u56fe\u7247-39.png 510w, http:\/\/www.sniper97.cn\/wp-content\/uploads\/2019\/12\/\u56fe\u7247-39-233x300.png 233w\" sizes=\"(max-width: 510px) 100vw, 510px\" \/><\/figure><\/div>\n\n\n<p>\u7136\u540e\u5de6\u53f6\u5b50\u5b9a\u4e49\u4e3a0\uff0c\u53f3\u53f6\u5b50\u5b9a\u4e49\u4e3a1\uff0c\u5373\u53ef\u627e\u51fa\u53d8\u957f\u7f16\u7801\u3002<\/p>\n\n\n<p>\u6784\u9020\u54c8\u592b\u66fc\u7f16\u7801\u4ee3\u7801\uff08\u53ea\u5199\u5230\u751f\u6210\u54c8\u592b\u66fc\u6811\uff09\uff1a<\/p>\n\n\n<pre class=\"wp-block-preformatted\">def huffman_code(self, data):<br \/>    <em>\"\"\"<br \/><\/em><em>    <\/em><em>\u751f\u6210\u54c8\u592b\u66fc\u7f16\u7801<br \/><\/em><em>    <\/em><strong><em>:param<\/em><\/strong><em> data:<br \/><\/em><em>    <\/em><strong><em>:return<\/em><\/strong><em>:<br \/><\/em><em>    \"\"\"<br \/><\/em><em>    <\/em>huffman_tree = self.build_huffman_tree(data)<br \/>    pass<br \/><br \/>def build_huffman_tree(self, data):<br \/>    <em>\"\"\"<br \/><\/em><em>    <\/em><em>\u6784\u9020\u54c8\u5f17\u66fc\u6811<br \/><\/em><em>    <\/em><strong><em>:param<\/em><\/strong><em> data:<br \/><\/em><em>    <\/em><strong><em>:return<\/em><\/strong><em>:<br \/><\/em><em>    \"\"\"<br \/><\/em><em>    <\/em>huffman_str = []<br \/>    huffman_tree = []<br \/><br \/>    def find_min():<br \/>        <em>\"\"\"<br \/><\/em><em>        <\/em><em>\u5bfb\u627e\u6700\u5c0f\u7684\u4e24\u4e2a\u70b9<br \/><\/em><em>        <\/em><strong><em>:return<\/em><\/strong><em>:<br \/><\/em><em>        \"\"\"<br \/><\/em><em>        <\/em>if len(data) == 1:<br \/>            return data[0], None<br \/>        min_data = float('inf')<br \/>        # \u6700\u5c0f\u70b9<br \/>        most_min = data[0]<br \/>        # \u6b21\u5c0f\u70b9<br \/>        secd_min = data[0]<br \/>        # \u904d\u5386\u5bfb\u627e\u6700\u5c0f\u70b9<br \/>        for each in data:<br \/>            if each[1] &lt; min_data:<br \/>                most_min = each<br \/>                min_data = each[1]<br \/>        data.remove(most_min)<br \/>        min_data = float('inf')<br \/>        # \u904d\u5386\u5bfb\u627e\u6700\u5c0f\u70b9<br \/>        for each in data:<br \/>            if each[1] &lt; min_data:<br \/>                secd_min = each<br \/>                min_data = each[1]<br \/>        data.remove(secd_min)<br \/>        # \u5c06\u8fd9\u4e24\u4e2a\u70b9\u7684\u6839\u52a0\u56de\u53bb<br \/>        data.append(['*', most_min[1] + secd_min[1]])<br \/><br \/>        return most_min, secd_min<br \/><br \/>    def connect_tree():<br \/>        <em>\"\"\"<br \/><\/em><em>        <\/em><em>\u8fde\u63a5\u6811<br \/><\/em><em>        <\/em><strong><em>:return<\/em><\/strong><em>:<br \/><\/em><em>        \"\"\"<br \/><\/em><em>        <\/em># \u6700\u5c0f\u70b9<br \/>        most_min = huffman_str[-1]<br \/>        # \u6b21\u5c0f\u70b9<br \/>        secd_min = huffman_str[-2]<br \/><br \/>        flag = most_min[1] + secd_min[1]<br \/>        root_idx = 0<br \/>        # \u904d\u5386\u5bfb\u627e\u6700\u5c0f\u4e24\u4e2a\u70b9\u7684\u6839<br \/>        for i in range(len(huffman_str) - 1, -1, -1):<br \/>            if huffman_str[i][1] == flag:<br \/>                root_idx = i<br \/>                break<br \/>            pass<br \/>        # \u8fde\u63a5\u5de6\u53f3\u5b50\u6811<br \/>        huffman_tree[root_idx].left = huffman_tree[-1]<br \/>        huffman_tree[root_idx].right = huffman_tree[-2]<br \/>        # \u79fb\u9664\u8fd9\u4e24\u4e2a\u70b9<br \/>        huffman_str.remove(most_min)<br \/>        huffman_str.remove(secd_min)<br \/>        huffman_tree.remove(huffman_tree[-1])<br \/>        huffman_tree.remove(huffman_tree[-1])<br \/>        pass<br \/><br \/>    # \u6784\u9020\u54c8\u592b\u66fc\u5b57\u7b26\u4e32\uff08\u56e0\u4e3a\u6ca1\u529e\u6cd5\u8fde\u6210\u6811\uff0c\u5148\u8ba1\u7b97\u54c8\u592b\u66fc\u6811\u7684\u5217\u8868\u8868\u793a\uff09<br \/>    for i in range(len(data)):<br \/>        most_min, secd_min = find_min()<br \/>        if secd_min is None:<br \/>            huffman_str.insert(0, most_min)<br \/>            continue<br \/>        huffman_str.insert(0, most_min)<br \/>        huffman_str.insert(0, secd_min)<br \/>        pass<br \/>    # \u5229\u7528\u5df2\u77e5\u7684\u54c8\u592b\u66fc\u987a\u5e8f\u6784\u9020\u54c8\u5f17\u66fc\u6811<br \/>    for each in huffman_str:<br \/>        huffman_tree.append(tree(each[1], None, None, None))<br \/>    for i in range(int(len(huffman_str) \/ 2)):<br \/>        connect_tree()<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u6c42\u89e3\u6700\u4f18\u5316\u95ee\u9898\u7684\u7b97\u6cd5\u901a\u5e38\u9700\u8981\u7ecf\u8fc7\u4e00\u7cfb\u5217\u7684\u6b65\u9aa4\uff0c\u5728\u6bcf\u4e2a\u6b65\u9aa4\u90fd\u9762\u4e34\u591a\u79cd\u9009\u62e9\u3002\u5bf9\u4e8e\u8bb8\u591a\u6700\u4f18\u5316\u95ee\u9898\uff0c\u4f7f\u7528\u52a8\u6001 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_mi_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[11],"tags":[],"views":6422,"_links":{"self":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/2598"}],"collection":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/comments?post=2598"}],"version-history":[{"count":0,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/2598\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/media?parent=2598"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/categories?post=2598"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/tags?post=2598"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}