❶ 0/1背包問題能不能使用貪心法解決
貪心演算法解決背包問題有幾種策略：
(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。
❷ 證明題：用解背包問題的貪心演算法解0-1背包問題時不一定得到最優解 急求！！
貪心演算法總是作出在當前看來是最好的選擇，即貪心演算法並不從整體最優解上加以考慮，它所作出的選擇只是在某種意義上的局部最優解。
背包問題可以用貪心演算法求解，而0-1背包問題卻不能用貪心演算法求解。
用貪心演算法求解背包問題的步驟是，首先計算每種物品單位重量的價值vi/wi；然
後，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包後，背包內的物品總量未超過c，則選擇單位重量價值次高的物
品並盡可能多地裝入背包。依此策略一直進行下去，直到背包裝滿為止。
在最後一步包裝不下時可能會分割物品，而0-1背包問題不能分割物品，故不一定得到最優解。
取一反例即可說明
❸ 請教我用python的貪心法做0/1背包問題
動態規劃，可以給你說下思路。
我們用一個二維的矩陣A來存儲中間結果，A[i][j]代表前i個物體裝入容量為j的背包時可以得到的最優解，相當於是原問題的一個子問題，然後我們就可以寫出遞推式來更新這個矩陣，具體可以參考下詳細的講解，網上的博客非常多不用我再寫一遍。
比如這種：http://zh.wikipedia.org/zh-cn/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98
先自己讀一遍吧，有問題可以再問。
❹ 用貪心演算法解決背包問題
用貪心演算法解決背包問題，首先要明白，結果不一定是全局最優的。對於貪心法而言，首先步驟是找到最優度量標准，我這里的演算法採用的最優度量標準是： 收益p/重量w 的值最大者優先放入背包中，所以有演算法如下：void GreedyKnapsack(float * x){ //前置條件：w[i]已按p[i]/w[i]的非增次序排列 float u=m; //u為背包剩餘載重量，初始時為m for(int i=0;i<n;i++) x[i]=0; //對解向量x初始化 for(i=0;i<n;i++){ //按最優度量標准選擇的分量 if(w[i]>u) break; x[i]=1.0; u=u-w[i]; } if(i<n) x[i]=u/w[i];}
❺ 01背包問題
能不能用性價比來做呢
動態規劃看不懂啊
----------------------------------------------------------------------
如果不是0-1問題的話，當然可以通過比較性價比來做，這時候可考慮用貪心演算法；但如果是0-1問題的話就不能單純「用性價比來做」了，因為有可能背包空出一大塊。舉個簡單的例子：一個背包的容量是10KG，
物品A重7KG，價值為14元，
物品B重6KG，價值為11元，
物品C中4KG，價值為7元，
從性價比來看，A最高，但是將A放到背包里以後，無法放進其他物品了，此時總價值為14元；顯然，本問題的最佳方案為將B、C放入背包，總價值為18元。
這就是0-1背包問題為什麼能用動態規劃演算法，而不能用貪心演算法的原因。共同學習:-D
❻ 貪心演算法解決特殊0-1背包問題
void 0_1_Knapsack(float w[], int n, float c,int x[]) //w[]為每個物品的重量，c為背包容量
{
int i;
for(i=1;i<=n;i++) x[i]=0;
for(i=1;i<=n;i++)
{
if(w[i]>c) break;
x[i]=1;
c-=w[i];
}
}
❼ C語言貪心演算法 背包問題
if(k!=i)
t=T[i];
T[i]=T[k];
T[k]=t;
交換操作的三步要用{}括起來,不然只有t=T[i];是if的執行語句