貪心演算法的背包問題

Ⅰ 求背包問題貪心演算法實例結果

找零錢問題：以人民幣1元，2元，5元，10元，20元，50元，100元為例，要求所找的張數最少
背包問題：假設物體重量W1，W2．．．Wn其對應的價值為P1，P2．．．Pn，物體可分割，求裝入重量限制為m的背包中的物體價值最大．可用P/W來解答．
#include<iostream>
#include<algorithm>
using namespace std;
struct good//表示物品的結構體
{
double p;//價值
double w;//重量
double r;//價值與重量的比
}a[2000];
double s,value,m;
int i,n;
bool bigger(good a,good b)
{
return a.r>b.r;
}
int main()
{
scanf("%d",&n);//物品個數
for (i=0;i<n;i++)
{
scanf("%lf%lf",&a[i].w,&a[i].p);
a[i].r=a[i].p/a[i].w;
}
sort(a,a+n,bigger);//調用sort排序函數，你大概不介意吧，按照價值與重量比排序貪心
scanf("%lf",&m);//讀入包的容量m
s=0;//包內現存貨品的重量
value=0;//包內現存貨品總價值
for (i=0;i<n&&s+a[i].w<=m;i++)
{
value+=a[i].p;
s+=a[i].w;
}
printf("The total value in the bag is %.2lf.\n",value);//輸出結果
return 0;
}

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

if(k!=i)
t=T[i];
T[i]=T[k];
T[k]=t;
交換操作的三步要用{}括起來,不然只有t=T[i];是if的執行語句

Ⅲ 用貪心演算法求解背包問題的最優解。

你這個是部分背包么？也就是說物品可以隨意分割？
那麼可以先算出單位重量物品的價值，然後只要從高價值到低價值放入就行了，按p[i]/w[i]降序排序，然後一件一件加，加滿為止！
貪心的思路是：加最少的重量得到更大的價值！
算出單位價值為{6,4,3,2,7,5,2}
加的順序即為5,1,6,2,3,4/7
如果重量不超過就全部都加，超過就加滿為止
不懂可問望採納！
推薦看dd_engi的背包九講，神級背包教程！在此膜拜dd_engi神牛~

Ⅳ 為什麼貪心演算法不能解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=

Ⅳ 請問各位大蝦:怎樣用貪心演算法解決背包問題

貪心只能解決物品可以分割的背包問題，01背包得用動態規劃求解

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

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

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

Ⅶ 貪心演算法解決特殊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];
}
}

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

[背包問題]有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
價值 10 40 30 50 35 40 30
分析：
目標函數： ∑pi最大
約束條件是裝入的物品總重量不超過背包容量：∑wi<=M( M=150)
（1）根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？
（2）每次挑選所佔重量最小的物品裝入是否能得到最優解？
（3）每次選取單位重量價值最大的物品，成為解本題的策略。 ?
值得注意的是，貪心演算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的演算法。
貪心演算法還是很常見的演算法之一，這是由於它簡單易行，構造貪心策略不是很困難。
可惜的是，它需要證明後才能真正運用到題目的演算法中。
一般來說，貪心演算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
對於例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：
（1）貪心策略：選取價值最大者。反例：
W=30
物品：A B C
重量：28 12 12
價值：30 20 20
根據策略，首先選取物品A，接下來就無法再選取了，可是，選取B、C則更好。
（2）貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。
（3）貪心策略：選取單位重量價值最大的物品。反例：
W=30
物品：A B C
重量：28 20 10
價值：28 20 10
根據策略，三種物品單位重量價值一樣，程序無法依據現有策略作出判斷，如果選擇A，則答案錯誤。

Ⅸ 用貪心演算法解決背包問題

用貪心演算法解決背包問題，首先要明白，結果不一定是全局最優的。對於貪心法而言，首先步驟是找到最優度量標准，我這里的演算法採用的最優度量標準是： 收益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];}

Ⅹ 貪心演算法背包問題

缺少物品的價值。