01揹包問題，關於C 01揹包問題

1樓：匿名使用者

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

2樓：匿名使用者

你好哦樓主~

很高興看到你的問題。

但是又很遺憾到現在還沒有人回答你的問題。也可能你現在已經在別的地方找到了答案，那就得恭喜你啦。

可能是你問的問題有些專業了，沒人會。或者別人沒有遇到或者接觸過你的問題，所以幫不了你。建議你去問題的相關論壇去求助，那裡的人通常比較多，也會比較熱心，能快點幫你解決問題。

希望我的回答能夠幫到你！

祝你好運。。

關於c++ 01揹包問題

3樓：物理公司的

1. 摘要

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

2. 介紹

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

3. 演算法思想:

貪心法的基本思路：

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

該演算法存在問題：

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

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

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

實現該演算法的過程：

在約束下最大。

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

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

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

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

//v[i,j]表示從前i項中取出來的裝入體積為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

struct goodinfo

;//物品資訊結構體

void insertionsort(goodinfo goods,int n)

goods[i+1]=goods[0];

}}//按物品效益，重量比值做升序排列

void bag(goodinfo goods,float m,int n)

if(i<=n)

goods[i].x=cu/goods[i].w;//該物品所要放的量

/*按物品編號做降序排列*/

for(j=2;j<=n;j++)}

01揹包問題

4樓：匿名使用者

就是所謂01揹包，一個物品只能被用一次，因此當狀態簡化為一維(即f)時，f[v]是從f[v - c[i]]

轉移而來，所以，為了保證只用一次就需要倒序列舉了。

二維狀態的時候就沒關係。

動態規劃解決01揹包問題思路

5樓：

用維陣列存放解每都優沒優結構叫態規劃

答案哪要看題目要求輸哪= =看題目規定揹包空間（消耗）

lz再看看吧根本沒理解01揹包

動態規劃01揹包問題的最優解

6樓：未の彼方

用一維陣列存放的解每個都最優。。不然沒有最優子結構還叫什麼動態規劃

答案是哪個要看你題目要求輸出哪個= =就是看你題目上規定的揹包空間大小（消耗）。

lz再好好看看吧。。你根本沒理解01揹包

7樓：匿名使用者

對，上面那位對，用一維陣列存放的解每個都最優。。

01揹包問題-動態規劃整理成c語言！謝謝！

8樓：征服歐洲

#include

int c[50][50];

int w[10],v[10];

int x[10];

int n;

void knapsack_dp(int n,int w);

void output_sack(int c[50][50],int k) ;

void knapsack_dp(int n,int w)else

c[i][k]=c[i-1][k];

} }} void output_sack(int c[50][50],int k) }

x[1]=(c[1][k]?1:0);

for(i=1;i<=n;i++)

printf("%4d",x[i]);

} void main()

printf("最優解為:\n");

output_sack(c,m);

system("pause");}

01揹包問題，關於C 01揹包問題

0 1揹包問題的測試資料

分佈估計演算法求解0 1揹包問題演算法的C語言程式

01揹包問題怎麼做？（我是小學生啦，簡單講解寫吧，我要參加noip我是愛聯學生

其他用戶還看了：