0/1背包客問題(0/1 Knapsack)

2 min readSep 17, 2020

這次提到的是動態規劃很經典的問題之一。

問題大致敘述如下：

今天小明要出門遠足，小明的背包只能夠承受4公斤的重量，但是小明想要帶很多玩具要帶出門。其中玩具有：
巴斯光年4公斤，受同學們的喜愛程度為90分。
胡迪3公斤，受同學們的喜愛程度為80分。
蛋頭先生1公斤，受同學們的喜愛程度為60分。
請問怎麼樣帶玩具可以受到朋友們最多的喜愛，而且也不能超出背包承受度？

這個題目應該不會太難理解，只是要轉成程式碼，就需要多花一些功夫了。

因為這個問題的解法不是那麼好理解，所以需要各位一些時間耐心的去理解，我一開始在學的時候，是也花了好幾天的時間才能了解他的意涵，本質上不會太難，只是需要時間消化。

之前也提到，當說到動態規劃，就要想到「表格紀錄」。

所以在這邊，我們要怎麼用表格做記錄呢？

以下用圖片來做說明。