假設(shè)你是一個(gè)小偷，背著一個(gè)可裝下 4 磅東西的背包，你可以偷竊的物品如下：

為了讓偷竊的商品價(jià)值最高，你該選擇哪些商品？

簡(jiǎn)單算法

最簡(jiǎn)單的算法是：嘗試各種可能的商品組合，并找出價(jià)值最高的組合。

這樣顯然是可行的，但是速度非常慢。在只有 3 件商品的情況下，你需要計(jì)算 8 個(gè)不同的集合；當(dāng)有 4 件商品的時(shí)候，你需要計(jì)算 16 個(gè)不同的集合。每增加一件商品，需要計(jì)算的集合數(shù)都將翻倍！這種算法的運(yùn)行時(shí)間是 O(2?)，真的是慢如蝸牛。

動(dòng)態(tài)規(guī)劃

解決這樣問(wèn)題的答案就是使用動(dòng)態(tài)規(guī)劃！下面來(lái)看看動(dòng)態(tài)規(guī)劃的工作原理。動(dòng)態(tài)規(guī)劃先解決子問(wèn)題，再逐步解決大問(wèn)題。

對(duì)于背包問(wèn)題，你先解決小背包（子背包）問(wèn)題，再逐步解決原來(lái)的問(wèn)題。

比較有趣的一句話是：每個(gè)動(dòng)態(tài)規(guī)劃都從一個(gè)網(wǎng)格開(kāi)始。

背包問(wèn)題的網(wǎng)格如下：

總結(jié)

以上是生活随笔為你收集整理的01背包算法图解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。