【背包問題】畢業季，怎麼打包行李最划算，動態規劃教你最優選擇

又是一年畢業季 計算機系大學生張三正愁着打包行李 還剩幾個寶貝散落在寢室裏 遊戲本電腦 平板 咖啡機 編程 競賽獎盃 還有他的避射機器人 除去行李箱和必備的文件 他最多還能塞下10公斤的物品 要在不超重的前提下帶回最有價值的東西 張三給5件物品稱好了重量 估了價值 列成表格 既然目標是總價值最大 那我用貪心算法 每一步都挑價值最大的 最昂貴的當屬1萬元的機器人 可惜它也最重 一塞進行李箱 幾乎就滿了 張三掃了一頁剩下的物品 電腦 咖啡機和平板三件加起來才9公斤 價值卻有11000 比機器人還值錢 他頓時意識到 只看價值高低 根本行不通 要不看單位價值 就是每公斤能值多少錢 他靈機一動 把每件物品的性價比算了一遍 發現平板最高 其次是電腦和獎盃 他正要拍板決定 卻發現這個組合 仍然沒有電腦咖啡機 平板價值高 看來局部最優 全局卻未必最優 靠貪心算法 是解決不了這次難題了 張三一拍桌子 管他什麼算法 我把所有情況都列出來還不行嗎 5個物品 每個要麼選要麼不選 總共就32種組合 暴力美舉一把也不算過分 室友李四站在他背後 忽然撲斥一笑 張三都畢業了 還在暴力美舉 張三扭過頭來 羞紅了臉 那你說該用什麼算法 李四邪魅一笑 一組物品 每個都有重量和價值 一個總重量限制 要挑出最大價值的組合 你說用什麼算法 張三一瞪 這不就是揹包問題嗎 解決它最有效的方法 就是動態規劃 動態規劃就是把大問題拆成小問題 一步步記錄小問題的結果 然後通過遞歸關係得到最優解 他立刻在紙上比劃 現在的大問題是行李限重10公斤 如何從5個物品裏選總價值最大 可以拆成兩種情況 比如是否選平板 如果選了 就變成行李箱限重9公斤空間 從剩下4件裏選最大價值 再加上平板的3000元 如果沒選 容量還是10公斤 直接看剩下4件的最優選法 然後這比一比 哪個大就選哪個 以此類推 等到行李箱容量爲0 或者物品數量爲0時 便能算出每個分支的最大價值 從中取最大的爲最優解 對頭 你這說的是遞歸解法 從最終目標開始 往前回溯 但俗話說遞歸是神的思維方式 遞推纔是人的思維方式 像我這種凡人 得從簡單的情況開始 一步步往後遞推 也能搞定它 我們用表格法來理解動態規劃 把列設爲箱子容量 從0公斤到10公斤 一共11列 行表示考慮了前幾件物品 從0件到5件 共6行 每個格子代表 在容量爲10公斤 考慮前2件物品時 所能獲得的最大價值 最開始啥都沒裝 容量也是0 那價值自然是0 也就是說 第一行和第一列全是0 表示基礎狀態 接着我們從第一件物品 平板開始考慮 對每一列做兩個判斷 先判斷能不能放 再判斷要不要放 如果當前容量小於1000個 平板放不進去 那這一格的值 就繼承上面那格的值 也就是箱子容量沒變 考慮前2件1個物品時的最大價值 如果容量大於等於1公斤 就比較平板 放和不放哪個更值錢 選擇不放 和之前說的放不進去 效果是一樣的 都要繼承上面格子的值 選擇放 那就先要把箱子容量控出來 再放進這個物品 也就是箱子容量 價值就是考慮前2件1個物品時的最大價值 加上當前物品的價值 容量1000克 能放平板價值3000元 容量2000克也能放 但只有平板一個物品 價值仍是3000 一直到10000克都是3000 第二件 獎盃 同樣每一列都判斷 容量1000克 獎盃太大 裝不下 只能繼承上面的值 也就是3000 容量2000克 剛好能裝 那就不放值是上面那格3000 放進去 箱子容量得先減去獎盃重量 變成0 差0千克時 前一件物品的值是0 加上獎盃2000 總共2000 兩者比較 顯然不放更值錢 寫3000 容量3000克 不放 上面那格是3000 放 先控制獎盃的重量 容量變成1000克 差那一格最大價值是3000 放上獎盃加2000 等於5000 兩者比較 選更大的 寫5000 張三越聽越起勁 一邊照着邏輯往下填 一邊感慨 原來動態規劃表格這麼好用 張三目光落在最右下角那一格 光顧着算最大價值了 這11000元 到底是由哪幾樣物品構成的呢 這不難 我們可以從結果反推回去 關鍵在於 當前格子的值 和上方格子的值 是否相同 要是一樣 說明這個物品沒放進箱子 是繼承了上一步的最優結果 如果不一樣 那就說明這個物品放進來了 張三恍然大悟 立刻順着李四的思路 從最後一格開始倒推 機器人這格和上方一樣 說明沒放 容量不變還是10千克 咖啡機這一格和上方不同 放 容量從10千克 減去4千克 變成6千克 電腦的格子也和上方不同 放了 容量從6千克 減去4千克 變成2千克 獎盃的格子和上方一樣 沒放 容量不變 平板的格子和上方不同 放了 容量從2千克 減去1千克 變成1千克 回到基礎狀態 張三驚呼 所以放進箱子裏的東西 是電腦 咖啡機和平板 這不正是我開始瞎猜的組合嗎 這回蒙對是運氣 但要是物品再多點呢 10件物品就有1024種組合 你還能一個個猜嗎 還是得靠咱們這張表 不靠窮舉 不靠貪心 只靠一套清晰的邏輯 從小問題推到大問題 每一格都在前面 所有最優角色的基礎上 做出的新選擇 我明白了 動態規劃的精髓 最優結果不是拍腦袋得出來的 而是一步步自己長出來的 張三滿意的收好行李箱 爲了表示感謝 把剩下的機器人和獎盃 轉給了李斯 李斯受寵若驚 一轉頭 看向自己的行李箱 他若有所思的提起了筆 也開始畫起了自己的動態規劃表 我是圖靈宇宙 講有溫度的故事 作爲有思考的科普 我們下期再見