A. 求動態規劃0-1背包演算法解釋
01背包問題
題目
有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。
基本思路
這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。
用子問題定義狀態：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態轉移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：「將前i件物品放入容量為v的背包中」這個子問題，若只考慮第i件物品的策略（放或不放），那麼就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那麼問題就轉化為「前i-1件物 品放入容量為v的背包中」，價值為f[i-1][v]；如果放第i件物品，那麼問題就轉化為「前i-1件物品放入剩下的容量為v-c[i]的背包中」，此時能獲得的最大價值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。
優化空間復雜度
以上方法的時間和空間復雜度均為O(VN)，其中時間復雜度應該已經不能再優化了，但空間復雜度卻可以優化到O。
先考慮上面講的基本思路如何實現，肯定是有一個主循環i=1..N，每次算出來二維數組f[i][0..V]的所有值。那麼，如果只用一個數組 f[0..V]，能不能保證第i次循環結束後f[v]中表示的就是我們定義的狀態f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]兩個子問題遞推而來，能否保證在推f[i][v]時（也即在第i次主循環中推f[v]時）能夠得到f[i-1][v]和f[i-1] [v-c[i]]的值呢？事實上，這要求在每次主循環中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c[i]]保存的是狀態 f[i-1][v-c[i]]的值。偽代碼如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當於我們的轉移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因為現在的f[v-c[i]]就相當於原來的f[i-1][v-c[i]]。如果將v的循環順序從上面的逆序改成順序的話，那麼則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案，故學習只用一維數組解01背包問題是十分必要的。
事實上，使用一維數組解01背包的程序在後面會被多次用到，所以這里抽象出一個處理一件01背包中的物品過程，以後的代碼中直接調用不加說明。
過程ZeroOnePack，表示處理一件01背包中的物品，兩個參數cost、weight分別表明這件物品的費用和價值。
procere ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
注意這個過程里的處理與前面給出的偽代碼有所不同。前面的示常式序寫成v=V..0是為了在程序中體現每個狀態都按照方程求解了，避免不必要的思維復雜度。而這里既然已經抽象成看作黑箱的過程了，就可以加入優化。費用為cost的物品不會影響狀態f[0..cost-1]，這是顯然的。
有了這個過程以後，01背包問題的偽代碼就可以這樣寫：
for i=1..N
ZeroOnePack(c[i],w[i]);
初始化的細節問題
我們看到的求最優解的背包問題題目中，事實上有兩種不太相同的問法。有的題目要求「恰好裝滿背包」時的最優解，有的題目則並沒有要求必須把背包裝滿。一種區別這兩種問法的實現方法是在初始化的時候有所不同。
如果是第一種問法，要求恰好裝滿背包，那麼在初始化時除了f[0]為0其它f[1..V]均設為-∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優解。
如果並沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應該將f[0..V]全部設為0。
為什麼呢？可以這樣理解：初始化的f數組事實上就是在沒有任何物品可以放入背包時的合法狀態。如果要求背包恰好裝滿，那麼此時只有容量為0的背包可能被價值為0的nothing「恰好裝滿」，其它容量的背包均沒有合法的解，屬於未定義的狀態，它們的值就都應該是-∞了。如果背包並非必須被裝滿，那麼 任何容量的背包都有一個合法解「什麼都不裝」，這個解的價值為0，所以初始時狀態的值也就全部為0了。
這個小技巧完全可以推廣到其它類型的背包問題，後面也就不再對進行狀態轉移之前的初始化進行講解。
一個常數優化
前面的偽代碼中有 for v=V..1，可以將這個循環的下限進行改進。
由於只需要最後f[v]的值，倒推前一個物品，其實只要知道f[v-w[n]]即可。以此類推，對以第j個背包，其實只需要知道到f[v-sum{w[j..n]}]即可，即代碼中的
for i=1..N
for v=V..0
可以改成
for i=1..n
bound=max{V-sum{w[i..n]},c[i]}
for v=V..bound
這對於V比較大時是有用的。
小結
01背包問題是最基本的背包問題，它包含了背包問題中設計狀態、方程的最基本思想，另外，別的類型的背包問題往往也可以轉換成01背包問題求解。故一定要仔細體會上面基本思路的得出方法，狀態轉移方程的意義，以及最後怎樣優化的空間復雜度。
B. 01背包 動態規劃演算法
嗯。。。錯誤上說了嘛，max的第二個參數錯了，原參數：V[i-1][j-w[i]]+V[i]，加數V[i]是int*類型的，當然不能和被加數相加啦
C. 用動態規劃演算法和貪婪演算法求解01背包問題的區別
首先這兩個演算法是用來分別解決不同類型的背包問題的，不存在哪個更優的問題。 當一件背包物品可以分割的時候，使用貪心演算法，按物品的單位體積的價值排序，從大到小取即可。 當一件背包物品不可分割的時候，（因為不可分割，所以就算按物品的單位體積的價值大的先取也不一定是最優解）此時使用貪心是不對的，應使用動態規劃。
D. matlab的遺傳演算法求解0-1整數規劃的程序
x = intlinprog(f,intcon,A,b,Aeq,beq)就可以了
用法舉例：
Write the objective function vector and vector of integervariables.
f = [-3;-2;-1];
intcon = 3;
Write the linear inequality constraints.
A = [1,1,1];
b = 7;
Write the linear equality constraints.
Aeq = [4,2,1];
beq = 12;
Write the bound constraints.
lb = zeros(3,1);
ub = [Inf;Inf;1]; % Enforces x(3) is binary
Call intlinprog.
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
E. 用動態規劃法解01背包問題的演算法時間復雜性
n*m
n是物品數量，m是背包容量的取值范圍
F. 線性規劃整數解有簡便方法嗎 線性規劃整數解除了用畫圖法還有什麼別的方法有隻用代數的方法嗎
整數線性規劃的解法總結
0-1整數線性規劃是整數線性規劃的特殊情況,在實際中有著廣泛的應用.雖然變數的取值只有兩個,但此類問題的求解卻意外的困難,下面把有關的一些解法總結一下.
1.窮舉法 把所有可能的解一一代入,然後比較滿足約束的解,使目標函數最達到最優的解是最優解.這不失為一種方法,但不是一種好方法.如果問題規模大,則無法在可接受的時間內求得最優解.這也是求解整數規劃的困難所在.
2.隱枚舉法I 是窮舉法的改進,其思路是先給出一個可行解,然後代入目標函數算出函數值得到一個上界（如果求最小值）或下界（如果是求最大值）.然後一一檢驗其它的解,如果該解大於上界或小於下界,則不用檢驗可行性,因為它不可能是最優解,否則的話就要檢驗可行性,如果是可行解,則修改上界或下界,繼續檢驗其它的解,否則不用修改上界或下界,直接檢驗其它的解.這種方法通過上界或下界來控制是否需要進行可行性檢驗,提高了效率.但是,要找可行解也得花一定的時間,當約束和變數較多時,工作量異常的大,退一步來說,即使可行解比較容易找到,但其產生的上界太大,或是下界太小,則其過濾的效果也不明顯.這是這種方法的缺陷.
3.隱枚舉法II 這種方法先把問題轉化成標准型,然後按照分枝定界法的思想,盡量少的檢驗可行解來尋找最優解.這種方法比較麻煩,我在這里也描述不清楚,過幾天理解透了再來寫這一部分.
4.隱枚舉法III 這是在程冬時,張聲年在江西電力職業技術學院學報上發表的一篇文章《關於0-1型整數規劃的若干問題》中提出來的,大致的思路是：把所有可能的解都代入目標函數算出值,然後把這些目標函數值進行排序,如果是求最大值,則降序排列,如果是求最小值則升序排列.然後按這個順序一個一個的檢驗對應的解的可行性,當碰到第一個可行解時即得到最優解,因為其它的解不會優於此解了.這種方法的缺陷也是明顯的,如果變數為N個,則需求2的N次個目標函數值,然後還要進行排序,這又是項工作量很大的工作,再一個就是,如果排序結果是把可行解排在最後一個,那還是得進行2的N次方次檢驗.
4.啟發式演算法 遺傳演算法,蟻群演算法等都可歸於此類.這都是隨機演算法,說白了就是聽天由命,即使算出了最優解你也不知道是不是最優解,因為此類演算法的收斂性都只是依概率收斂的,真正在算的過程中是否已得到最優只有上帝知道.啟發式演算法是萬不得已的情況下才使用的,我們用這種方法只能保證得到的解比其它方法得到的好,但不一定就說得到了最優了.
0-1規劃的求解方法還在研究之中,也許你會發現一個有效的演算法.
G. 多目標線性規劃的常用求解演算法有哪些
多目標決策主要有以下幾種方法：
（1）化多為少法：將多目標問題化成只有一個或二個目標的問題，然後用簡單的決策方法求解，最常用的是線性加權和法。
（2）分層序列法：將所有目標按其重要性程度依次排序，先求出第一個最重要的目標的最優解，然後在保證前一目標最優解的前提下依次求下一目標的最優解，一直求到最後一個目標為止。
（3）直接求非劣解法：先求出一組非劣解，然後按事先確定好的評價標准從中找出一個滿意的解。
（4）目標規劃法：對於每一個目標都事先給定一個期望值，然後在滿足系統一定約束條件下，找出與目標期望值最近的解。
（5）多屬性效用法：各個目標均用表示效用程度大小的效用函數表示，通過效用函數構成多目標的綜合效用函數，以此來評價各個可行方案的優劣。
（6）層次分析法：把目標體系結構予以展開，求得目標與決策方案的計量關系。
（7）重排序法：把原來的不好比較的非劣解通過其他辦法使其排出優劣次序來。
（8）多目標群決策和多目標模糊決策等
H. 用動態規劃演算法怎樣求解01背包問題
動態規劃主要解決的是多階段的決策問題。
01背包中，狀態為背包剩餘的容量，階段是每一個物品，決策是是否選擇當前的物品。
所以用動態規劃來解決是非常貼切的。
我們設f[V]表示已經使用容量為V時所能獲得的最大價值，w[i]表示i物品的質量，c[i]表示i物品的價值。
for(inti=1;i<=n;i++)
for(intj=V;j>=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+c[i]);
這便是所謂的一個狀態轉移方程。
f[j]表示在已經使用容量為j時的最大價值，f[j-w[i]]表示在已經使用容量為j-w[i]時的最大價值。
f[j]可以由f[j-w[i]]這個狀態轉移到達，表示選取w[i]這個物品，並從而獲得價值為c[i]。
而每次f[j]會在選與不選中決策選出最優的方案。
從每一個物品，也就是每一個階段的局部最優推出最後的全局最優值。這樣就解決了01背包問題
I. MATLAB軟體怎樣計算0,1規劃
最近在折騰01規劃，顯然lingo在這方面非常的強大，matlab有一個01的規劃函數工具，但是是線性函數的，網上很多的。
matlab最近在做題瘋了1000*100的01矩陣，matlab經常越界，蒙特卡羅計算時間受不了或者貪心演算法只是局部最優。但是lingo就無視了。同學用lingo的很快就搞定了。