① 關於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;
}
}