1樓：每天一罐黑瓶紅牛
小白嘗試解答一下。揹包問題給我的感覺就是，看了答案好像挺明白，可一細琢磨，就暈了。我在這裡給出我的一種解釋。
假設：我會一種魔法，這種魔法能夠幫我進行最優選擇。我不需要知道魔法原理。
V[i][j]: 我只考慮前i個物品。當容量為j時，我使用魔法，魔法進行最優選擇，從中選出某些物品，使得包裹的價值最大。
注意：至於怎麼選擇的，我不知道，交給魔法。比如i等於5，魔法有可能選了第1個，第4個。
不用關心魔法如何選擇。問，就是魔法。
V[i][j] = max(V[i-1][j], V[i-1][j-weight[i]] + value[i])
如何理解上式？
我現在已經知道V[i-1][j]了。當我開始考慮第i個物品，把它加入我的候選清單，使用魔法。Case1:
魔法當然可能不選擇第i個物品，所以依然等於V[i-1][j]。即雖然現在多了乙個選項i，神奇的魔法不鳥它，認為它沒用或者價效比很低（比如選了i就要把其它的移出去），仍然只從前i-1個物品中做出了最優選擇。
Case2: 魔法決定把物品i選進來。既然現在選物品i，那麼之前的選擇組合就要變一下。
為什麼？因為空間也許放不下了。怎麼變呢？
魔法首先當然得保證i能放進去。好，魔法已經認定物品i在最終選擇裡，那麼可操作的空間只有j-weight[i]了。魔法接下來要做的事就是在j-weight[i]的空間裡再選擇一次，從前i-1個物品中找到個最優組合。
這個最優組合的價值當然就是V[i-1][j-weight[i]]（因為魔法之前已經找到過這個值）。那麼總價值就是V[i-1][j-weight[i]] + value[i]。
比較兩種情況，選更優的。
2樓：
我跟你有一模一樣的困惑，總感覺這種遍歷方法不能組合到所有的情況，但是這方法卻是對的。
直覺上來說遞迴是絕對可行的，因為每種嘗試都建立在之前所匹配的的組合中了。
乍一看狀態轉移方程很直觀，仔細一想感覺又不對，再想想又像是某種演算法化簡之後的結果，想到最後就只好來知乎了，囧！
3樓：
初學者的一點點理解
先考慮最簡單的情況：
只從前1個物品中取物品，揹包容量為1。要使揹包總價值最大，第1個物品取不取？
如果取第1個物品：那麼揹包剩餘容量減少，揹包的總價值為「物品1的價值」加上「剩餘容量從裝前0個物品中取，能取得的最大總價值」。
如果不取第1個物品：揹包剩餘容量不變。那麼揹包的總價值為「從前0個物品中能裝入揹包的最大總價值」。
比較「取第1個物品」和「不取第1個物品」時，揹包的總價值，決定取不取第1個物品。
然後，
還是考慮只從前1個物品中取物品，但揹包容量為2,3,...,v(書包的最大容量)時。要使揹包總價值最大，第1個物品取不取？（分析和上面一樣）
然後，
考慮只從前2個物品中取物品，揹包容量為1,2,3,...,v(書包的最大容量)時。要使揹包總價值最大，第2個物品取不取？
如果取第2個物品：那麼揹包剩餘容量減少，揹包的總價值為「物品2的價值」加上「剩餘容量從裝前1個物品中取，能取得的最大總價值」。
如果不取第2個物品，揹包剩餘容量不變。那麼揹包的總價值為「剩餘容量從裝前2個物品中取，能取得的最大總價值」。
比較「取第2個物品」和「不取第2個物品」時，揹包的總價值，決定取不取第2個物品。
這也解決了只從前2個物品中取物品，揹包容量為1,2,3,...,v(書包的最大容量)時。要使揹包總價值最大，該怎麼取組合價值最大的問題。
最後同理推廣到只從前2,...,n個物品中取物品，揹包容量為1,2,3,...,v(書包的最大容量)時。
要使揹包總價值最大，該怎麼取組合價值最大的問題。
4樓：tfatdos
簡單來說就是分解問題
就拿第乙個物品來說
總的問題可以分解為兩個子問題
5樓：遙月
最容易理解的是回溯法，也就是用遞迴的方法把所有可能的結果都嘗試一遍（每個物品都可能被取或不取，共 種情況），每一次得到新的結果，都要和當前的最優解比較以判斷是否要更新當前最優解。
假設有n個物品，（剩餘）容量為c
那麼依次從第乙個物品開始直至最後乙個物品：
對於物品i有兩種可能：
1） 2）
對於1）有兩種選擇：
a)將物品i放入揹包，同時剩餘容量變為c-weight[i],價值加上profit[i]，繼續遞迴物品i+1；
b)物品i不放入揹包，剩餘容量不變繼續遞迴物品i+1；
對於2）只能選擇情況（1）的b方案
終止條件是i==n，若 ,則將物品n放入揹包，價值加上profit[n]並更新當前最優解;
當然這種方法沒有採取優化，可能會有重複解並且複雜度太高。可以採用剪枝的方式記錄下已經求到的值來中止遞迴。
第二種方法是採用動態規劃，通過一張n*c大小表記錄所有的情況，這個方法的理解就比回溯法那個要難一些。其思想是利用之前已得到的資訊直接求解當前待求的資訊。
首先對錶進行部分初始化：
可以認為是先拿最後乙個物品，對於當前剩餘容量的不同（0-capcity）得到表最後一行的值
接下來考慮倒數第二個物品，主要的方法還是和初始化操作一樣的，根據容量的不同採取不同的策略，不過每次得到的值都應是當前的最優值，所以需要乙個max的操作
有了對回溯法的理解，理解這個也是同樣的道理，若當前剩餘容量小於當前物品重量，那麼就不能將物品放入揹包，此處的值等於i+1處的值，反之，因為表是倒著構造的，求一下拿/不拿中的最大值就行了~
最後一步，只用算乙個揹包容量下的結果就行了
返回的就是fArray[0][capcity]
針對題主 @讓神經飛一會兒 的問題：
1:是要想獲得當前的最大價值，裝進第i個物品後使得v[i][j]獲得最大價值，第i個物品只要能裝下，不應該是一定裝嗎？我知道我這樣就成了貪心演算法
當前物品i能裝下不是一定要裝，因為後面的情況是未知的（無論是上面哪種方法都是如此）
因為考慮到物品i的價效比以及容量的情況。
2:那麼假如i為最後乙個物品了，能裝下，那麼有沒有可能max()公式會得出來不裝第i個物品價值比較大，這樣不是錯誤的嗎？
因為你在裝揹包的時候之前的選擇已經確定的了，當剩下最後乙個物品時，如果還有容量，不裝白不裝，肯定不會出現你所說的問題。
3:每次對第i個物品進行選擇時，我都不知道後面的那些物品價值如何，為何通過這個公式我就那麼確定這個物品要不要裝進去，我總覺得需要窮舉然後比較才能找到最優解。
參考動態規劃的方法，倒著來想，對於當前物品在所有容量的情況下都能夠得到最優解。
如果用回溯的話，你當然無法確定當前物品要不要裝進去，必須得分別對每種情況繼續分析
6樓：顧然
建議你去讀一下Introduction to algorithms裡關於動規的章節，你的幾個問題讓人感覺你並不明白什麼是動態規劃。
它其實已經是對解空間的「所有」方案進行了比對，選了乙個最優的。之所以比暴力搜尋快，是因為這類問題有大量的公共子問題，所以我們可以用表來記錄下這些子問題的解，來避免重複計算，所以又可以稱它為記憶化搜尋。
首先說一下你的1和2的問題，其實是一樣的，你忽略了一點，如果第i個物品能裝下，且裝上了，揹包的剩餘體積就變小了，可能導致的後果是前面的一些高價效比的物品裝不上了。所以關於這個方程，你過分關注了i這個階段，而忽略了j這一維。
關於3，上面已經說了，dp實際上列舉了整個解空間。
dp能解決的問題還有乙個特性，就是最優子結構， 最優子結構的意思是乙個問題的最優解方案必然是由它的子問題的最優解方案構成的（或者說演變而成的）。你可以認為這個特性讓我們在解空間搜尋樹上做了大量的剪枝 。
用01揹包來解釋的話，就是V[i][j]其實是乙個和原問題相同的子問題，就是有i個物品，容量為j的揹包，怎麼放最優。如果第i個物品不放，那麼問題就變成了V[i-1][j],如果第i個物品放，那麼問題就變成了V[i-1][j-weight[i]]。而且如果MAX的取值是前者（也就是不放更優），也就是說v[i][j]的最優解是由V[i-1][j]演變而來的，那麼則一定有V[i-1][j]也是最優解。
否則我們可以找乙個更好的取而代之。
那麼你可能會有疑問，為什麼乙個問題T的最優解方案是由它的子問題S的最優解方案構成的呢。因為S->T所做的決策和決策所產生的收益是與S無關的。而由S->T我們可以認為是由很多階段構成的，每個階段的決策和收益只與當前階段的一些東西相關，比方說第i個物品的體積和價值。
所以一定只能是最優解來更新最優解。
如此下來，dp實則是做了剪枝的有記憶的搜尋。
7樓：彌頭毫
我覺得使題主困惑的地方在於，我們對v[i][j]的定義是：用前i個物品，在揹包限制為j的情況下，最多能拿多少價值。
動態規劃的每一步，不是「面對第i個物品，選擇拿或不拿」；而是「面對第1～i這一堆物品，揹包容量限制為j，最後那第i個物品拿還是不拿「。
關於三個具體問題：
1:是要想獲得當前的最大價值，裝進第i個物品後使得v[i][j]獲得最大價值，第i個物品只要能裝下，不應該是一定裝嗎？我知道我這樣就成了貪心演算法,
第i個物品能裝下，不是一定拿。
拿第i個物品的好處是得到它的價值，代價是揹包空間只剩下j-w[i]，
不拿第i個物品的好處是有更多的揹包空間去裝前1～(i-1)這一堆物品，代價是沒有得到物品i的價值。
這兩個選項就是max()函式裡兩項的意義。
2:那麼假如 i為最後乙個物品了，能裝下，那麼有沒有可能max()公式會得出來不裝第i個物品價值比較大，這樣不是錯誤的嗎？
如果max()函式告訴你不裝第i個物品價值比較大，說明揹包空間用來裝1～(i-1)這一堆物品的一部分比較話划算，就不必花空間去裝第i個了。
3:每次對第i個物品進行選擇時，我都不知道後面的那些物品價值如何，為何通過這個公式我就那麼確定這個物品要不要裝進去，我總覺得需要窮舉然後比較才能找到最優解。
這個公式只告訴你有第1～i這些物品，並且揹包容量限制為j時的最優解，i之後的其它物品對它來說並不存在。
對01揹包 基礎演算法動態規劃入門題不理解 怎麼辦？
朱星滔 先不管獲得最大價值的方案是啥，直接考慮最後一步 反正是從n個物品裡面選，最後乙個裝的物品可能是第1個，第2個，也可能是第n個，甚至可能乙個都裝不下。假設最後乙個裝的物品是第i個，對於體積為j的揹包 如果體積j v i 才能把物品裝進來，那麼怎麼用程式語言描述呢？if j v i f i j ...
物體體積和價值正相關的01揹包問題有什麼好的解法麼？
題主應該好好看看knapsack這本書。線性01規劃問題已經被研究的非常成熟了。semidefinite relaxation,lagrangian relaxation效果都不錯啊。但天下沒有免費的午餐，每個具體問題都需要仔細推理驗證，這才是重點。 花落憶流年 貪婪演算法通常用單位體積的價值來衡量...
學生如何盡量減輕揹包對體態的摧殘？
umbreak 最簡單有效的辦法題主也說了，是減輕負重。不能不帶書，那麼去列印店把教材切割成一章一章或兩章兩章的，膠裝加封面，上哪章帶哪冊，好看又輕便。去年同時上 內科學 外科學 經常連堂，一本800 1000頁左右吧，就是這麼活下來的。拆裝前拆裝後 鐘文 發現很多背單肩包引起頸肩部不適的患者，日常...