貪心演算法背包問題c

Ⅰ 貪心演算法的例題分析

例題1、
[0-1背包問題]有一個背包，背包容量是M=150。有7個物品，物品不可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
價值 10$ 40$ 30$ 50$ 35$ 40$ 30$
分析：
目標函數：∑pi最大
約束條件是裝入的物品總重量不超過背包容量：∑wi<=M(M=150）
⑴根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？
⑵每次挑選所佔重量最小的物品裝入是否能得到最優解？
⑶每次選取單位重量價值最大的物品，成為解本題的策略。
值得注意的是，貪心演算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的演算法。
貪心演算法還是很常見的演算法之一，這是由於它簡單易行，構造貪心策略不是很困難。
可惜的是，它需要證明後才能真正運用到題目的演算法中。
一般來說，貪心演算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
對於例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：
⑴貪心策略：選取價值最大者。
反例：
W=30
物品：A B C
重量：28 12 12
價值：30 20 20
根據策略，首先選取物品A，接下來就無法再選取了，可是，選取B、C則更好。
⑵貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。
⑶貪心策略：選取單位重量價值最大的物品。
反例：
W=30
物品：A B C
重量：28 20 10
價值：28 20 10
根據策略，三種物品單位重量價值一樣，程序無法依據現有策略作出判斷，如果選擇A，則答案錯誤。
【注意：如果物品可以分割為任意大小，那麼策略3可得最優解】
對於選取單位重量價值最大的物品這個策略，可以再加一條優化的規則：對於單位重量價值一樣的，則優先選擇重量小的！這樣，上面的反例就解決了。
但是，如果題目是如下所示，這個策略就也不行了。
W=40
物品：A B C
重量：25 20 15
價值：25 20 15
附：本題是個DP問題，用貪心法並不一定可以求得最優解，以後了解了動態規劃演算法後本題就有了新的解法。
例題2、
馬踏棋盤的貪心演算法
123041-23 XX
【問題描述】
馬的遍歷問題。在8×8方格的棋盤上，從任意指定方格出發，為馬尋找一條走遍棋盤每一格並且只經過一次的一條路徑。
【初步設計】
首先這是一個搜索問題，運用深度優先搜索進行求解。演算法如下：
⒈ 輸入初始位置坐標x,y；
⒉ 步驟 c:
如果c> 64輸出一個解，返回上一步驟c--
（x,y) ← c
計算(x,y）的八個方位的子結點，選出那些可行的子結點
循環遍歷所有可行子結點，步驟c++重復2
顯然⑵是一個遞歸調用的過程，大致如下：
C++程序： #defineN8voiddfs(intx,inty,intcount){inti,tx,ty;if(count>N*N){output_solution();//輸出一個解return;}for(i=0;i<8;i++){tx=hn[i].x;//hn[]保存八個方位子結點ty=hn[i].y;s[tx][ty]=count;dfs(tx,ty,count+1);//遞歸調用s[tx][ty]=0;}}Pascal程序： ProgramYS;ConstFXx:array[1..8]of-2..2=（1,2,2,1,-1,-2,-2,-1）；FXy:array[1..8]of-2..2=（2,1,-1,-2,-2,-1,1,2）；VarRoad:array[1..10,1..10]ofinteger;x,y,x1,y1,total:integer;ProcereFind(x,y:integer);varNx,Ny,i:integer;BeginFori:=1to8dobegin{8個方向}If(x+FXx[i]in[1..8])and(y+FXy[i]in[1..8])Then{確定新坐標是否越界}IfRoad[x+Fxx[i],y+Fxy[i]]=0Thenbegin{判斷是否走過}Nx:=x+FXx[i];Ny:=y+FXy[i];Road[Nx,Ny]:=1;{建立新坐標}If(Nx=x1）and(Ny=y1）Theninc(total)elseFind(Nx,Ny);{遞歸}Road[Nx,Ny]:=0{回朔}endendEnd;BEGIN{Main}Total:=0;FillChar(Road,sizeof(road),0);Readln(x,y);{讀入開始坐標}Readln(x1,y1）；{讀入結束坐標}If(x>10）or(y>10）or(x1>10）or(y1>10）Thenwriteln('Error'){判斷是否越界}ElseFind(x,y);Writeln('Total:',total){打出總數}END.這樣做是完全可行的，它輸入的是全部解，但是馬遍歷當8×8時解是非常之多的，用天文數字形容也不為過，這樣一來求解的過程就非常慢，並且出一個解也非常慢。
怎麼才能快速地得到部分解呢？
【貪心演算法】
其實馬踏棋盤的問題很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一個有名的演算法。在每個結點對其子結點進行選取時，優先選擇『出口』最小的進行搜索，『出口』的意思是在這些子結點中它們的可行子結點的個數，也就是『孫子』結點越少的越優先跳，為什麼要這樣選取，這是一種局部調整最優的做法，如果優先選擇出口多的子結點，那出口少的子結點就會越來越多，很可能出現『死』結點（顧名思義就是沒有出口又沒有跳過的結點），這樣對下面的搜索純粹是徒勞，這樣會浪費很多無用的時間，反過來如果每次都優先選擇出口少的結點跳，那出口少的結點就會越來越少，這樣跳成功的機會就更大一些。這種演算法稱為為貪心演算法，也叫貪婪演算法或啟發式演算法，它對整個求解過程的局部做最優調整，它只適用於求較優解或者部分解，而不能求最優解。這樣的調整方法叫貪心策略，至於什麼問題需要什麼樣的貪心策略是不確定的，具體問題具體分析。實驗可以證明馬遍歷問題在運用到了上面的貪心策略之後求解速率有非常明顯的提高，如果只要求出一個解甚至不用回溯就可以完成，因為在這個演算法提出的時候世界上還沒有計算機，這種方法完全可以用手工求出解來，其效率可想而知。

Ⅱ 動態規劃背包問題與貪心演算法哪個更優

首先這兩個演算法是用來分別解決不同類型的背包問題的，不存在哪個更優的問題。
當一件背包物品可以分割的時候，使用貪心演算法，按物品的單位體積的價值排序，從大到小取即可。
當一件背包物品不可分割的時候，（因為不可分割，所以就算按物品的單位體積的價值大的先取也不一定是最優解）此時使用貪心是不對的，應使用動態規劃。

Ⅲ 求完全背包問題的代碼(C語言或C++版)或演算法

背包問題小結- []2006-07-28

做到背包問題覺得很有意思，寫寫看看。
完全背包問題可以用貪心演算法。
代碼如下：

program bag1;
const maxn=10;
var
goods:array[1..maxn,1..3] of integer;
s:array[1..maxn] of real;
i,j:integer;
m,n:integer;
y:integer;
x:real;
function max:integer;
var m:real;
i,j:integer;
begin
m:=0;
for i:=1 to n do
if (goods[i,3]=0) and (m max:=j;
end;

procere choose;
var i,j:integer;

begin
while y begin
if y begin
i:=max;
if m>=y+goods[i,1] then begin goods[i,3]:=1;x:=x+goods[i,2];y:=y+goods[i,1];end else
begin
x:=x+(m-y)*s[i];
y:=m;
end;
end;
end;
end;

begin
fillchar(goods,sizeof(goods),0);
assign(input,'b.txt');
reset(input);
readln(m,n);
for j:=1 to n do
read(goods[j,1]);
readln;
for j:=1 to n do
read(goods[j,2]);
for j:=1 to n do
s[j]:=goods[j,2]/goods[j,1];

close(input);
choose;
writeln(x:5:2);
end.
編得不是很好 ^-^ 獻丑了。

我來說說0/1背包問題。
狀態：當前物品n
算符：j=0（當前物品不放入背包） 或 j=1（當前物品放入背包）
這就很好說了，還是把yes函數一改，問題OK了。
代碼如下：

program bag2;
const maxn=10;
var i:integer;
goods:array[1..maxn,1..3] of integer;{原始數據}
s:array[1..maxn] of integer;{當前的狀態}
r:array[1..maxn] of integer;{當前的總質量}
m:integer;{背包容量}
max:integer;{物品個數}
procere try(n:integer);
var j:integer;

{function yes:boolean;
var k:integer;
t:integer;
mn:integer;
begin
mn:=0;
t:=goods[n,3];
goods[n,3]:=j;
for k:=1 to n do
if goods[k,3]=1 then inc(mn,goods[k,1]);
goods[n,3]:=t;
if mn>m then yes:=false else yes:=true;
end;}

begin
if n=max+1 then begin if x for i:=1 to max do s[i]:=goods[i,3]; {保存最優解}end
end else
begin
if r[n-1]>m then exit;{已超過背包總容量}
for j:=1 downto 0 do
begin
if j=1 then r[n]:=r[n-1]+goods[n,1];
if j=0 then r[n]:=r[n]-goods[n,1];
if {yes}r[n]<=m then begin goods[n,3]:=j;try(n+1);goods[n,3]:=0;end
end;
end;
end;

begin
assign(input,'b.txt');
reset(input);
readln(m,max);
for i:=1 to max do
read(goods[i,1]);
readln;
for i:=1 to max do
read(goods[i,2]);
close(input);
try(1);
for i:=1 to 7 do
write(s[i]:3);
writeln;
writeln(x);
end.

用yes 函數要從頭到當前求已裝入背包物品的總質量，時間效率不高。所以我們引入r[n]數組來記錄當前背包總質量（很好用！）注意用r[n-1]>m來做剪枝，以再次提高時間效率。

DC跟我說可以用二進制解此類問題。我覺得很有創意，也說說。比如8個物品，每個物品有0/1兩種狀態所以我們從(00000000)(二進制 )到（11111111）（二進制）循環即可。然後在分離十進制數對應起來即可。但在實際的操作中發現效率比回溯還低，我想有兩方面的原因：1、顯而易見，不可能做剪枝。2、每一次結果都要從1到8求和十效率降低。不過這確實是一種很新穎的演算法。

Ⅳ C語言 貪心演算法求背包問題

是你的冒泡排序出了問題~

你吧 原來的1-2-3號按照東西的價值重新排列現在的1-2-3對應原來的2-1-3了
所以 你輸出的時候是按 1-2-3輸出的話 就等於第一個是原來的X2 第二個是X1第三個是X3
而且你的冒泡排序用錯了 只比較了 P[0]/K[0]和P[1]/K[1] P[1]/K[1]和P[2]/K[2]
周一我去學校幫你重新改改 我家的機器沒有C++
周一晚上我會上傳答案~我最近正好也要做演算法的作業~
#include <stdio.h>
#include <math.h>
#define N 50

float find(float p[N],float w[N],float x[N] ,float M,int n) /*先放單位價值量大的物體，再考慮小的物體*/
{
int i;
float maxprice;
for (i = 0; i < n; i++)
x[i] = 0;
i = 0;
maxprice=0;
while (i < n && w[i] < M)
{
M=M-w[i];
x[i] =w[i]; /* 表示放入數量 */
maxprice=maxprice+p[i];
x[n-1]=M;
i++;
}
if (i < n &&M> 0)
{
maxprice=maxprice+p[i]*x[i]/w[i];
i++;
}
return maxprice;
}

int main()
{
int n,flag=1;
float temp,M,w[N],p[N],x[N];
int a[N],b[N];
int k,j,l=0;
printf(

Ⅳ 貪心演算法 部分背包問題

這道題是dp的思想啦，動態規劃

(1)背包問題最優值的結構

動態規劃的逆向思維法的第一步是刻畫一個最優值的結構，如果我們能分析出一個問題的最優值包含其子問題的最優值，問題的這種性質稱為最優子結構。一個問題的最優子結構性質是該問題可以使用動態規劃的顯著特徵。

對一個負重能力為m的背包，如果我們選擇裝入一個第 i 種物品，那麼原背包問題就轉化為負重能力為 m-w[i] 的子背包問題。原背包問題的最優值包含這個子背包問題的最優值。若我們用背包的負重能力來劃分狀態，令狀態變數s[k]表示負重能力為k的背包，那麼s[m]的值只取決於s[k](k≤m)的值。因此背包問題具有最優子結構。

(2)遞歸地定義最優值

動態規劃的逆向思維法的第二步是根據各個子問題的最優值來遞歸地定義原問題的最優值。對背包問題而言，有狀態轉移方程：

／max{s[k-w[i]]+v[i]}(其中1≤i≤n，且k-w[i]≥0)

s[k]= 若k>0且存在1≤i≤n使k-w[i]≥0，

＼ 0 否則。

有了計算各個子問題的最優值的遞歸式，我們就可以直接編寫對應的程序。下述的函數knapsack是輸入背包的負重能力k，返回對應的子背包問題的最優值s[k]：

Ⅵ 用貪心演算法能求解背包問題嗎為什麼,理由是什麼

一般的貪心策略都會造成解的丟失,動態規劃則是相當於枚舉了所有的解.

如果你有一個很好的貪心策略,背包問題也能用貪心策略來解決.但是,你是很難找到一個很好的貪心策略的.

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

Ⅷ 背包問題的演算法

3.2 背包問題
背包問題有三種

1.部分背包問題

一個旅行者有一個最多能用m公斤的背包，現在有n種物品，它們的總重量分別是W1，W2，...,Wn,它們的總價值分別為C1,C2,...,Cn.求旅行者能獲得最大總價值。

解決問題的方法是貪心演算法:將C1/W1,C2/W2,...Cn/Wn,從大到小排序,不停地選擇價值與重量比最大的放人背包直到放滿為止.

2.0/1背包

一個旅行者有一個最多能用m公斤的背包，現在有n件物品，它們的重量分別是W1，W2，...,Wn,它們的價值分別為C1,C2,...,Cn.若每種物品只有一件求旅行者能獲得最大總價值。

<1>分析說明:

顯然這個題可用深度優先方法對每件物品進行枚舉(選或不選用0,1控制).

程序簡單,但是當n的值很大的時候不能滿足時間要求，時間復雜度為O（2n）。按遞歸的思想我們可以把問題分解為子問題,使用遞歸函數

設 f(i，x)表示前i件物品，總重量不超過x的最優價值

則 f（i，x）=max(f(i－1，x-W[i])+C[i]，f（i－1，x））

f（n，m）即為最優解，邊界條件為f（0，x）＝0 ，f(i,0)=0;

動態規劃方法(順推法)程序如下:

程序如下：

program knapsack02;
const maxm=200;maxn=30;
type ar=array[1..maxn] of integer;
var m,n,j,i:integer;
c,w:ar;
f:array[0..maxn,0..maxm] of integer;
function max(x,y:integer):integer;
begin
if x>y then max:=x else max:=y;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
for i:=1 to m do f(0,i):=0;
for i:=1 to n do f(i,0):=0;

for i:=1 to n do
for j:=1 to m do
begin
if j>=w[i] then f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])
else f[i,j]:=f[i-1,j];
end;
writeln(f[n,m]);
end.

使用二維數組存儲各子問題時方便，但當maxm較大時如maxn=2000時不能定義二維數組f,怎麼辦,其實可以用一維數組,但是上述中j:=1 to m 要改為j:=m downto 1,為什麼?請大家自己解決。

3.完全背包問題

一個旅行者有一個最多能用m公斤的背包，現在有n種物品，每件的重量分別是W1，W2，...,Wn,

每件的價值分別為C1,C2,...,Cn.若的每種物品的件數足夠多.

求旅行者能獲得的最大總價值。

本問題的數學模型如下：

設 f(x)表示重量不超過x公斤的最大價值，

則 f(x）=max{f(x-w[i])+c[i]} 當x>=w[i] 1<=i<=n

程序如下:（順推法）

program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
f:array[0..maxm] of integer;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
f(0):=0;
for i:=1 to m do
for j:=1 to n do
begin
if i>=w[j] then t:=f[i-w[j]]+c[j];
if t>f[i] then f[i]:=t
end;
writeln(f[m]);
end.

Ⅸ 貪心演算法解決0-1背包問題得到的解通常是最優解或者近似最優解嗎

這種規則，價值最大的物品首先被裝入（假設有足夠容量），然後是下一個價值最大的物品，如此繼續下去。這種策略不能保證得到最優解。例如，考慮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], 比最優解