動態規劃01揹包動態規劃01揹包c

1樓：灰姑娘的霸氣

#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");}

2樓：258369甘世傑

#include

using namespace std;

int v[100],w[100],f[1000],n,tot;

int main()

我沒執行直接寫的，問題應該不大

3樓：匿名使用者

01揹包問題是動態規

動態規劃中，01揹包問題演算法的基礎思想是，在已知的更小情況下的最優解條件下，如何判斷下個最優解，以此類推，得到所有最優解。示例**如下

#include

using namespace std;

int main()

int v[1001][101];

for(int i=0;i<=t;i++)for (int i=0;i<=m;i++)for (int j=1;j<=m;j++)}cout<

關於c++ 01揹包問題

4樓：物理公司的

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揹包問題思路

5樓：

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

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

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

動態規劃01揹包動態規劃01揹包c

揹包問題的問法變化，0 1揹包問題的多種解法程式碼（動態規劃貪心法回溯法分支限界法）

有一種雙肩揹包，揹包的帶子很長，包的形狀是正方形的，請問那包

怎樣清洗揹包，戶外揹包要如何清洗

動態規劃01揹包動態規劃01揹包c

揹包問題的問法變化，0 1揹包問題的多種解法程式碼（動態規劃 貪心法 回溯法 分支限界法）

有一種雙肩揹包，揹包的帶子很長，包的形狀是正方形的，請問那包

怎樣清洗揹包，戶外揹包要如何清洗

相關推薦

揹包問題的問法變化，0 1揹包問題的多種解法程式碼（動態規劃貪心法回溯法分支限界法）