一、問題描述
有n個物品，第i個物品的體積為ci，價值為wi，還有一個容積為v的背包，現在往背包中裝物品，怎樣才能使得背包内的物品價值最大。
二、分析思路
步驟1：用函數的形式來表示題目結果。
設f(x,v)=y，表示有x個物品，容積為v的背包的最大價值。那麼本題要求的便是f(n,v)。
步驟2：分析遞推情況。
遞推情況分析主要是考慮一般的情況，即f(i)與f(i-1)等之間的關系。
那麼本題我們考慮在背包容量限制為v的前提下，有i個物品和i-1個之間的關系。
假如我們現在已經知道f(i-1,v)的值即要裝i-1個物品達到的最大值，接下來分析是否要裝第i個物品，隻有兩種情況裝或不裝。如果不裝第i個物品的話，那麼體積限制還是v，最大價值是f(i-1,v)，如果要裝第i個物品，那麼i-1個物品的體積限制就應該是v-ci,最大價值應該是i-1個物品的最大值加上第i個物品的價值即f(i-1,v-ci) + wi
綜上，我們得到如下的遞推公式：
f(i, v) = max{ f(i-1, v), f(i-1, v-ci) + wi }
步驟3：算法實作。
如您對該算法感興趣，“算法與程式設計之美”公衆号将為您做後續講解。
三、總結
本文給大家介紹了利用動态規劃算法求解01背包的問題，您掌握了嗎？背包問題除了01背包之外還有很多其他類型的變種，如完全背包等，後續部落格将逐一的介紹。
