01背包問題的演算法解決

Ⅰ 01背包問題

演算法分析

對於背包問題，通常的處理方法是搜索。
用遞歸來完成搜索，演算法設計如下：
function Make( i {處理到第i件物品} , j{剩餘的空間為j}:integer) :integer;
初始時i=m , j=背包總容量
begin
if i:=0 then
Make:=0;
if j>=wi then (背包剩餘空間可以放下物品 i )
r1:=Make(i-1,j-wi)+v; (第i件物品放入所能得到的價值 )
r2:=Make(i-1,j)(第i件物品不放所能得到的價值 )
Make:=max{r1,r2}
end;
這個演算法的時間復雜度是O(2^n)，我們可以做一些簡單的優化。
由於本題中的所有物品的體積均為整數，經過幾次的選擇後背包的剩餘空間可能會相等，在搜索中會重復計算這些結點，所以，如果我們把搜索過程中計算過的結點的值記錄下來，以保證不重復計算的話，速度就會提高很多。這是簡單?quot;以空間換時間"。
我們發現，由於這些計算過程中會出現重疊的結點，符合動態規劃中子問題重疊的性質。
同時，可以看出如果通過第N次選擇得到的是一個最優解的話，那麼第N-1次選擇的結果一定也是一個最優解。這符合動態規劃中最優子問題的性質。
考慮用動態規劃的方法來解決，這里的：
階段是：在前N件物品中，選取若干件物品放入背包中；
狀態是：在前N件物品中，選取若干件物品放入所剩空間為W的背包中的所能獲得的最大價值；
決策是：第N件物品放或者不放；
由此可以寫出動態轉移方程：
我們用f[i,j]表示在前 i 件物品中選擇若干件放在所剩空間為 j 的背包里所能獲得的最大價值
f[i,j]=max{f[i-1,j-Wi]+Pi (j>=Wi), f[i-1,j]}
這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：「將前i件物品放入容量為v的背包中」這個子問題，若只考慮第i件物品的策略（放或不放），那麼就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那麼問題就轉化為「前i-1件物品放入容量為v的背包中」，價值為f[v]；如果放第i件物品，那麼問題就轉化為「前i-1件物品放入剩下的容量為v-c的背包中」，此時能獲得的最大價值就是f[v-c]再加上通過放入第i件物品獲得的價值w。
這樣，我們可以自底向上地得出在前M件物品中取出若干件放進背包能獲得的最大價值，也就是f[m,w]
演算法設計如下：
procere Make;
begin
for i:=0 to w do
f[0,i]:=0;
for i:=1 to m do
for j:=0 to w do begin
f[i,j]:=f[i-1,j];
if (j>=w) and (f[i-1,j-w]+v>f[i,j]) then
f[i,j]:=f[i-1,j-w]+v;
end;
writeln(f[m,wt]);
end;
由於是用了一個二重循環，這個演算法的時間復雜度是O（n*w)。而用搜索的時候，當出現最壞的情況，也就是所有的結點都沒有重疊，那麼它的時間復雜度是O（2^n)。看上去前者要快很多。但是，可以發現在搜索中計算過的結點在動態規劃中也全都要計算，而且這里算得更多（有一些在最後沒有派上用場的結點我們也必須計算），在這一點上好像是矛盾的。
事實上，由於我們定下的前提是：所有的結點都沒有重疊。也就是說，任意N件物品的重量相加都不能相等，而所有物品的重量又都是整數，那末這個時候W的最小值是：1+2+2^2+2^3+……+2^n-1=2^n -1
此時n*w>2^n，動態規劃比搜索還要慢~~|||||||所以，其實背包的總容量W和重疊的結點的個數是有關的。
考慮能不能不計算那些多餘的結點……
優化時間復雜度
以上方法的時間和空間復雜度均為O(N*V)，其中時間復雜度基本已經不能再優化了，但空間復雜度卻可以優化到O(V)。
先考慮上面講的基本思路如何實現，肯定是有一個主循環i=1..N，每次算出來二維數組f[0..V]的所有值。那麼，如果只用一個數組f[0..V]，能不能保證第i次循環結束後f[v]中表示的就是我們定義的狀態f[v]呢？f[v]是由f[v]和f[v-c]兩個子問題遞推而來，能否保證在推f[v]時（也即在第i次主循環中推f[v]時）能夠得到f[v]和f[v-c]的值呢？事實上，這要求在每次主循環中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c]保存的是狀態f[v-c]的值。偽代碼如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c]+w};
其中的f[v]=max{f[v],f[v-c]}一句恰就相當於我們的轉移方程f[v]=max{f[v],f[v-c]}，因為現在的f[v-c]就相當於原來的f[v-c]。如果將v的循環順序從上面的逆序改成順序的話，那麼則成了f[v]由f[v-c]推知，與本題意不符，但它卻是另一個重要的背包問題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,w);
初始化的細節問題

我們看到的求最優解的背包問題題目中，事實上有兩種不太相同的問法。有的題目要求「恰好裝滿背包」時的最優解，有的題目則並沒有要求必須把背包裝滿。一種區別這兩種問法的實現方法是在初始化的時候有所不同。
如果是第一種問法，要求恰好裝滿背包，那麼在初始化時除了f[0]為0其它f[1..V]均設為-∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優解。
如果並沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應該將f[0..V]全部設為0。
為什麼呢？可以這樣理解：初始化的f數組事實上就是在沒有任何物品可以放入背包時的合法狀態。如果要求背包恰好裝滿，那麼此時只有容量為0的背包可能被價值為0的nothing「恰好裝滿」，其它容量的背包均沒有合法的解，屬於未定義的狀態，它們的值就都應該是-∞了。如果背包並非必須被裝滿，那麼任何容量的背包都有一個合法解「什麼都不裝」，這個解的價值為0，所以初始時狀態的值也就全部為0了。
這個小技巧完全可以推廣到其它類型的背包問題，後面也就不再對進行狀態轉移之前的初始化進行講解

Ⅱ @回溯法求解0-1背包問題，TSP旅行商問題有妙招，從全排列說起

回溯法是一種解決問題的策略，尤其適用於像0-1背包問題和TSP旅行商問題這樣的組合優化問題。讓我們一步步來看。

首先，回溯法從探明問題的解空間開始。以全排列問題為例，對集合{1, 2, 3}，我們通過枚舉所有可能的排列組合，如從1開始，後續有{1, 2}和{1, 3}兩種選擇，繼續遞歸下去，直到所有排列都被考慮。最終得到解空間：{{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}}。

對於0-1背包問題，物品的選擇形成一個決策樹，每件物品的選擇或不選擇都構成一個可能的解。例如，6件物品的解空間可能包括{11, 10, 01, 00}等。通過遞歸地嘗試所有組合，直到達到背包容量限制或所有物品都選擇或不選擇。

TSP旅行商問題則是尋找一個路徑，讓旅行商訪問所有城市且僅一次，返回起點。比如從北京出發，計算北京到上海、合肥等城市的最短路線，形成一個完整的回溯搜索過程。

使用回溯法，我們可以設計演算法來求解這些問題。對於每個問題，我們都會有一個判別函數來決定當前選擇是否可行，然後迭代或回溯，直到找到最優解。通過編程實現，如Python代碼，可以實際執行這些演算法並得到結果。

總結一下，回溯法在0-1背包問題和TSP問題中，通過構建解空間、設計策略和執行搜索，幫助我們找到最優解。現在你了解了這種方法的基本原理和應用。

Ⅲ 計算機演算法分析考試：動態規劃0-1背包問題，怎麼算

問題描述：
給定n種物品和一背包，物品i的重量是wi，其價值為vi，背包的容量為C。問應如何選擇裝入背包的物品（物品不能分割），使得裝入背包中物品的總價值最大?

抽象描述如下：
x[n]:表示物品的選擇，x[i]=1表示選擇放進物品i到背包中。

Ⅳ 用動態規劃演算法怎樣求解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背包問題

Ⅳ 關於C++ 01背包問題

1.摘要

以背包問題為例，介紹了貪心法與動態規劃的關系以及兩個方案在解決背包問題上的比較。貪心法什麼時候能取到最優界並無一般理論，但對於普通背包問題我們有一個完美的結果——貪心法可取到最優解。介紹了其它一些對背包問題的研究或者拓展。

2.介紹

貪心演算法是我們在《演算法設計技巧與分析》這門課中所學習到的幾種重要的演算法之一，顧名思義，貪心演算法總是作出在當前看來最好的選擇。也就是該演算法並不從整體最優考慮，它所作出的選擇只是在某種意義上的從局部的最優選擇，尋找到解決問題的次優解的方法。雖然我們希望貪心演算法得到的最終結果也是整體最優的，但是在某些情況下，該演算法得到的只是問題的最優解的近似。

3.演算法思想:

貪心法的基本思路：

——從問題的某一個初始解出發逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某演算法中的某一步不能再繼續前進時，演算法停止。

該演算法存在問題：

1.不能保證求得的最後解是最佳的；

2.不能用來求最大或最小解問題；

3.只能求滿足某些約束條件的可行解的范圍。

實現該演算法的過程：

在約束下最大。

(2)動態規劃解決方案：是解決0/1背包問題的最優解

(i)若i=0或j=0,V[i,j] = 0

(ii)若j<si, V[i,j] = V[i-1,j](僅用最優的方法，選取前i-1項物品裝入體積為j的背包，因為第i項體積大於j,裝不下這一項，所以背包裡面的i-1項就達到最大值)

(iii)若i>0和j>=si, Max{V[i-1,j],V[i-1,j-si]+vi} (第一種情況是包中的i-1項已經達到最大值，第二種情況是i-1項佔j-si的體積再加上第i項的總的價值，取這兩種情況的最大值。)

//sj和vj分別為第j項物品的體積和價值，C是總體積限制。

//V[i,j]表示從前i項{u1,u2,…,un}中取出來的裝入體積為j的背包的物品的最大//價值。[13]

（3）貪心演算法解決背包問題有幾種策略：

(i)一種貪婪准則為：從剩餘的物品中，選出可以裝入背包的價值最大的物品，利用這種規則，價值最大的物品首先被裝入（假設有足夠容量），然後是下一個價值最大的物品，如此繼續下去。這種策略不能保證得到最優解。例如，考慮n=2, w=[100,10,10], p =[20,15,15], c = 105。當利用價值貪婪准則時，獲得的解為x= [ 1 , 0 , 0 ]，這種方案的總價值為2 0。而最優解為[ 0 , 1 , 1 ]，其總價值為3 0。

(ii)另一種方案是重量貪婪准則是：從剩下的物品中選擇可裝入背包的重量最小的物品。雖然這種規則對於前面的例子能產生最優解，但在一般情況下則不一定能得到最優解。考慮n= 2 ,w=[10,20], p=[5,100], c= 2 5。當利用重量貪婪策略時，獲得的解為x =[1,0],比最優解[ 0 , 1 ]要差。

(iii)還有一種貪婪准則，就是我們教材上提到的，認為，每一項計算yi=vi/si,即該項值和大小的比，再按比值的降序來排序，從第一項開始裝背包，然後是第二項，依次類推，盡可能的多放，直到裝滿背包。

有的參考資料也稱為價值密度pi/wi貪婪演算法。這種策略也不能保證得到最優解。利用此策略試解n= 3 ,w=[20,15,15], p=[40,25,25], c=30時的最優解。雖然按pi /wi非遞（增）減的次序裝入物品不能保證得到最優解，但它是一個直覺上近似的解。

而且這是解決普通背包問題的最優解，因為在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。

如圖1，大體上說明了動態規劃解決的0／1背包問題和貪心演算法解決的問題之間的區別，

圖1

（4）貪心演算法解決背包問題的演算法實現：

代碼如下：

#include<iostream.h>
structgoodinfo
{
floatp;//物品效益
floatw;//物品重量
floatX;//物品該放的數量
intflag;//物品編號
};//物品信息結構體
voidInsertionsort(goodinfogoods[],intn)
{//插入排序，按pi/wi價值收益進行排序，一般教材上按冒泡排序
intj,i;
for(j=2;j<=n;j++)
{
goods[0]=goods[j];
i=j-1;
while(goods[0].p>goods[i].p)
{
goods[i+1]=goods[i];
i--;
}
goods[i+1]=goods[0];
}
}//按物品效益，重量比值做升序排列
voidbag(goodinfogoods[],floatM,intn)
{

floatcu;
inti,j;
for(i=1;i<=n;i++)
goods[i].X=0;
cu=M;//背包剩餘容量
for(i=1;i<n;i++)
{
if(goods[i].w>cu)//當該物品重量大與剩餘容量跳出
break;
goods[i].X=1;
cu=cu-goods[i].w;//確定背包新的剩餘容量
}
if(i<=n)
goods[i].X=cu/goods[i].w;//該物品所要放的量
/*按物品編號做降序排列*/
for(j=2;j<=n;j++)
{
goods[0]=goods[j];
i=j-1;
while(goods[0].flag<goods[i].flag)
{
goods[i+1]=goods[i];
i--;
}
goods[i+1]=goods[0];
}
///////////////////////////////////////////
cout<<"最優解為:"<<endl;
for(i=1;i<=n;i++)
{
cout<<"第"<<i<<"件物品要放:";
cout<<goods[i].X<<endl;
}
}
voidmain()
{
cout<<"|--------運用貪心法解背包問題---------|"<<endl;
intj,n;floatM;
goodinfo*goods;//定義一個指針
while(j)
{
cout<<"請輸入物品的總數量：";
cin>>n;
goods=newstructgoodinfo[n+1];//
cout<<"請輸入背包的最大容量：";
cin>>M;
cout<<endl;
inti;
for(i=1;i<=n;i++)
{goods[i].flag=i;
cout<<"請輸入第"<<i<<"件物品的重量:";
cin>>goods[i].w;
cout<<"請輸入第"<<i<<"件物品的效益:";
cin>>goods[i].p;
goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比
cout<<endl;

}
Insertionsort(goods,n);
bag(goods,M,n);
cout<<"press<1>torunagian"<<endl;
cout<<"press<0>toexit"<<endl;
cin>>j;
}
}