① 背包問題的貪心演算法C＋＋
為啥不用動態規劃呢？
背包的貪心法是每次都選擇收益最大，如果包還能容納，就放入包裡面，並把這個物品去掉。
② 貪心演算法 部分背包問題
[背包問題]有一個背包，背包容量是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，則答案錯誤。
③ 貪心演算法中的背包問題求解答。C++代碼
排序應該下面這樣寫
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(a[j]<a[j+1]))
{
//互換
temp = w[j];
w[j]=w[j+1];
w[j+1]= temp;
}
}
}
④ C語言貪心演算法 背包問題
if(k!=i)
t=T[i];
T[i]=T[k];
T[k]=t;
交換操作的三步要用{}括起來,不然只有t=T[i];是if的執行語句
⑤ 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(
⑥ 0-1背包問題的多種解法代碼（動態規劃、貪心法、回溯法、分支限界法）
一.動態規劃求解0-1背包問題
/************************************************************************/
/* 0-1背包問題：
/* 給定n種物品和一個背包
/* 物品i的重量為wi，其價值為vi
/* 背包的容量為c
/* 應如何選擇裝入背包的物品，使得裝入背包中的物品
/* 的總價值最大？
/* 註：在選擇裝入背包的物品時，對物品i只有兩種選擇，
/* 即裝入或不裝入背包。不能將物品i裝入多次，也
/* 不能只裝入部分的物品i。
/*
/* 1. 0-1背包問題的形式化描述：
/* 給定c>0, wi>0, vi>0, 0<=i<=n，要求找到一個n元的
/* 0-1向量(x1, x2, ..., xn), 使得：
/* max sum_{i=1 to n} (vi*xi),且滿足如下約束：
/* (1) sum_{i=1 to n} (wi*xi) <= c
/* (2) xi∈{0, 1}, 1<=i<=n
/*
/* 2. 0-1背包問題的求解
/* 0-1背包問題具有最優子結構性質和子問題重疊性質，適於
/* 採用動態規劃方法求解
/*
/* 2.1 最優子結構性質
/* 設(y1,y2,...,yn)是給定0-1背包問題的一個最優解，則必有
/* 結論，(y2,y3,...,yn)是如下子問題的一個最優解：
/* max sum_{i=2 to n} (vi*xi)
/* (1) sum_{i=2 to n} (wi*xi) <= c - w1*y1
/* (2) xi∈{0, 1}, 2<=i<=n
/* 因為如若不然，則該子問題存在一個最優解(z2,z3,...,zn)，
/* 而(y2,y3,...,yn)不是其最優解。那麼有：
/* sum_{i=2 to n} (vi*zi) > sum_{i=2 to n} (vi*yi)
/* 且，w1*y1 + sum_{i=2 to n} (wi*zi) <= c
/* 進一步有：
/* v1*y1 + sum_{i=2 to n} (vi*zi) > sum_{i=1 to n} (vi*yi)
/* w1*y1 + sum_{i=2 to n} (wi*zi) <= c
/* 這說明：(y1,z2,z3,...zn)是所給0-1背包問題的更優解，那麼
/* 說明(y1,y2,...,yn)不是問題的最優解，與前提矛盾，所以最優
/* 子結構性質成立。
/*
/* 2.2 子問題重疊性質
/* 設所給0-1背包問題的子問題 P(i,j)為：
/* max sum_{k=i to n} (vk*xk)
/* (1) sum_{k=i to n} (wk*xk) <= j
/* (2) xk∈{0, 1}, i<=k<=n
/* 問題P(i,j)是背包容量為j、可選物品為i,i+1,...,n時的子問題
/* 設m(i,j)是子問題P(i,j)的最優值，即最大總價值。則根據最優
/* 子結構性質，可以建立m(i,j)的遞歸式：
/* a. 遞歸初始 m(n,j)
/* //背包容量為j、可選物品只有n，若背包容量j大於物品n的
/* //重量，則直接裝入；否則無法裝入。
/* m(n,j) = vn, j>=wn
/* m(n,j) = 0, 0<=j<wn
/* b. 遞歸式 m(i,j)
/* //背包容量為j、可選物品為i,i+1,...,n
/* //如果背包容量j<wi，則根本裝不進物品i，所以有：
/* m(i,j) = m(i+1,j), 0<=j<wi
/* //如果j>=wi，則在不裝物品i和裝入物品i之間做出選擇
/* 不裝物品i的最優值：m(i+1,j)
/* 裝入物品i的最優值：m(i+1, j-wi) + vi
/* 所以：
/* m(i,j) = max {m(i+1,j), m(i+1, j-wi) + vi}, j>=wi
/*
/************************************************************************/
#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))
template <typename Type>
void Knapsack(Type* v, int *w, int c, int n, Type **m)
{
//遞歸初始條件
int jMax = min(w[n] - 1, c);
for (int j=0; j<=jMax; j++) {
m[n][j] = 0;
}
for (j=w[n]; j<=c; j++) {
m[n][j] = v[n];
}
//i從2到n-1，分別對j>=wi和0<=j<wi即使m(i,j)
for (int i=n-1; i>1; i--) {
jMax = min(w[i] - 1, c);
for (int j=0; j<=jMax; j++) {
m[i][j] = m[i+1][j];
}
for (j=w[i]; j<=c; j++) {
m[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
}
}
m[1][c] = m[2][c];
if (c >= w[1]) {
m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);
}
}
template <typename Type>
void TraceBack(Type **m, int *w, int c, int n, int* x)
{
for (int i=1; i<n; i++) {
if(m[i][c] == m[i+1][c]) x[i] = 0;
else {
x[i] = 1;
c -= w[i];
}
}
x[n] = (m[n][c])? 1:0;
}
int main(int argc, char* argv[])
{
int n = 5;
int w[6] = {-1, 2, 2, 6, 5, 4};
int v[6] = {-1, 6, 3, 5, 4, 6};
int c = 10;
int **ppm = new int*[n+1];
for (int i=0; i<n+1; i++) {
ppm[i] = new int[c+1];
}
int x[6];
Knapsack<int>(v, w, c, n, ppm);
TraceBack<int>(ppm, w, c, n, x);
return 0;
}
二.貪心演算法求解0-1背包問題
1.貪心法的基本思路：
——從問題的某一個初始解出發逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某演算法中的某一步不能再繼續前進時，演算法停止。
該演算法存在問題：
1).不能保證求得的最後解是最佳的；
2).不能用來求最大或最小解問題；
3).只能求滿足某些約束條件的可行解的范圍。
實現該演算法的過程：
從問題的某一初始解出發；
while 能朝給定總目標前進一步 do
求出可行解的一個解元素；
由所有解元素組合成問題的一個可行解；
2.例題分析
1).[背包問題]有一個背包，背包容量是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）每次選取單位容量價值最大的物品，成為解本題的策略。
<程序代碼:>(環境:c++)
#include<iostream.h>
#define max 100 //最多物品數
void sort (int n,float a[max],float b[max]) //按價值密度排序
{
int j,h,k;
float t1,t2,t3,c[max];
for(k=1;k<=n;k++)
c[k]=a[k]/b[k];
for(h=1;h<n;h++)
for(j=1;j<=n-h;j++)
if(c[j]<c[j+1])
{t1=a[j];a[j]=a[j+1];a[j+1]=t1;
t2=b[j];b[j]=b[j+1];b[j+1]=t2;
t3=c[j];c[j]=c[j+1];c[j+1]=t3;
}
}
void knapsack(int n,float limitw,float v[max],float w[max],int x[max])
{float c1; //c1為背包剩餘可裝載重量
int i;
sort(n,v,w); //物品按價值密度排序
c1=limitw;
for(i=1;i<=n;i++)
{
if(w[i]>c1)break;
x[i]=1; //x[i]為1時，物品i在解中
c1=c1-w[i];
}
}
void main()
{int n,i,x[max];
float v[max],w[max],totalv=0,totalw=0,limitw;
cout<<"請輸入n和limitw:";
cin>>n >>limitw;
for(i=1;i<=n;i++)
x[i]=0; //物品選擇情況表初始化為0
cout<<"請依次輸入物品的價值："<<endl;
for(i=1;i<=n;i++)
cin>>v[i];
cout<<endl;
cout<<"請依次輸入物品的重量："<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<endl;
knapsack (n,limitw,v,w,x);
cout<<"the selection is:";
for(i=1;i<=n;i++)
{
cout<<x[i];
if(x[i]==1)
totalw=totalw+w[i];
}
cout<<endl;
cout<<"背包的總重量為："<<totalw<<endl; //背包所裝載總重量
cout<<"背包的總價值為："<<totalv<<endl; //背包的總價值
}
三.回溯演算法求解0-1背包問題
1.0-l背包問題是子集選取問題。
一般情況下，0-1背包問題是NP難題。0-1背包
問題的解空間可用子集樹表示。解0-1背包問題的回溯法與裝載問題的回溯法十分類
似。在搜索解空間樹時，只要其左兒子結點是一個可行結點，搜索就進入其左子樹。當
右子樹有可能包含最優解時才進入右子樹搜索。否則將右子樹剪去。設r是當前剩餘
物品價值總和；cp是當前價值；bestp是當前最優價值。當cp+r≤bestp時，可剪去右
子樹。計算右子樹中解的上界的更好方法是將剩餘物品依其單位重量價值排序，然後
依次裝入物品，直至裝不下時，再裝入該物品的一部分而裝滿背包。由此得到的價值是
右子樹中解的上界。
2.解決辦法思路：
為了便於計算上界，可先將物品依其單位重量價值從大到小排序，此後只要順序考
察各物品即可。在實現時，由bound計算當前結點處的上界。在搜索解空間樹時，只要其左兒子節點是一個可行結點，搜索就進入左子樹，在右子樹中有可能包含最優解是才進入右子樹搜索。否則將右子樹剪去。
回溯法是一個既帶有系統性又帶有跳躍性的的搜索演算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。演算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的演算法稱為回溯法，它適用於解一些組合數較大的問題。
2.演算法框架：
a.問題的解空間：應用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應到少包含問題的一個（最優）解。
b.回溯法的基本思想：確定了解空間的組織結構後，回溯法就從開始結點（根結點）出發，以深度優先的方式搜索整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，並成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。換句話說，這個結點不再是一個活結點。此時，應往回移動（回溯）至最近的一個活結點處，並使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。
3.運用回溯法解題通常包含以下三個步驟：
a.針對所給問題，定義問題的解空間；
b.確定易於搜索的解空間結構；
c.以深度優先的方式搜索解空間，並且在搜索過程中用剪枝函數避免無效搜索；
#include<iostream>
using namespace std;
class Knap
{
friend int Knapsack(int p[],int w[],int c,int n );
public:
void print()
{
for(int m=1;m<=n;m++)
{
cout<<bestx[m]<<" ";
}
cout<<endl;
};
private:
int Bound(int i);
void Backtrack(int i);
int c;//背包容量
int n; //物品數
int *w;//物品重量數組
int *p;//物品價值數組
int cw;//當前重量
int cp;//當前價值
int bestp;//當前最優值
int *bestx;//當前最優解
int *x;//當前解
};
int Knap::Bound(int i)
{
//計算上界
int cleft=c-cw;//剩餘容量
int b=cp;
//以物品單位重量價值遞減序裝入物品
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
b+=p[i];
i++;
}
//裝滿背包
if(i<=n)
b+=p[i]/w[i]*cleft;
return b;
}
void Knap::Backtrack(int i)
{
if(i>n)
{
if(bestp<cp)
{
for(int j=1;j<=n;j++)
bestx[j]=x[j];
bestp=cp;
}
return;
}
if(cw+w[i]<=c) //搜索左子樹
{
x[i]=1;
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cw-=w[i];
cp-=p[i];
}
if(Bound(i+1)>bestp)//搜索右子樹
{
x[i]=0;
Backtrack(i+1);
}
}
class Object
{
friend int Knapsack(int p[],int w[],int c,int n);
public:
int operator<=(Object a)const
{
return (d>=a.d);
}
private:
int ID;
float d;
};
int Knapsack(int p[],int w[],int c,int n)
{
//為Knap::Backtrack初始化
int W=0;
int P=0;
int i=1;
Object *Q=new Object[n];
for(i=1;i<=n;i++)
{
Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
P+=p[i];
W+=w[i];
}
if(W<=c)
return P;//裝入所有物品
//依物品單位重量排序
float f;
for( i=0;i<n;i++)
for(int j=i;j<n;j++)
{
if(Q[i].d<Q[j].d)
{
f=Q[i].d;
Q[i].d=Q[j].d;
Q[j].d=f;
}
}
Knap K;
K.p = new int[n+1];
K.w = new int[n+1];
K.x = new int[n+1];
K.bestx = new int[n+1];
K.x[0]=0;
K.bestx[0]=0;
for( i=1;i<=n;i++)
{
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
}
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
//回溯搜索
K.Backtrack(1);
K.print();
delete [] Q;
delete [] K.w;
delete [] K.p;
return K.bestp;
}
void main()
{
int *p;
int *w;
int c=0;
int n=0;
int i=0;
char k;
cout<<"0-1背包問題——回溯法 "<<endl;
cout<<" by zbqplayer "<<endl;
while(k)
{
cout<<"請輸入背包容量(c)："<<endl;
cin>>c;
cout<<"請輸入物品的個數(n)："<<endl;
cin>>n;
p=new int[n+1];
w=new int[n+1];
p[0]=0;
w[0]=0;
cout<<"請輸入物品的價值(p)："<<endl;
for(i=1;i<=n;i++)
cin>>p[i];
cout<<"請輸入物品的重量(w)："<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<"最優解為(bestx)："<<endl;
cout<<"最優值為(bestp)："<<endl;
cout<<Knapsack(p,w,c,n)<<endl;
cout<<"[s] 重新開始"<<endl;
cout<<"[q] 退出"<<endl;
cin>>k;
}
四.分支限界法求解0-1背包問題
1.問題描述：已知有N個物品和一個可以容納M重量的背包，每種物品I的重量為WEIGHT，一個只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的總效益最大。
2.設計思想與分析：對物品的選取與否構成一棵解樹，左子樹表示不裝入，右表示裝入，通過檢索問題的解樹得出最優解，並用結點上界殺死不符合要求的結點。
#include <iostream.h>
struct good
{
int weight;
int benefit;
int flag;//是否可以裝入標記
};
int number=0;//物品數量
int upbound=0;
int curp=0, curw=0;//當前效益值與重量
int maxweight=0;
good *bag=NULL;
void Init_good()
{
bag=new good [number];
for(int i=0; i<number; i++)
{
cout<<"請輸入第件"<<i+1<<"物品的重量:";
cin>>bag[i].weight;
cout<<"請輸入第件"<<i+1<<"物品的效益:";
cin>>bag[i].benefit;
bag[i].flag=0;//初始標志為不裝入背包
cout<<endl;
}
}
int getbound(int num, int *bound_u)//返回本結點的c限界和u限界
{
for(int w=curw, p=curp; num<number && (w+bag[num].weight)<=maxweight; num++)
{
w=w+bag[num].weight;
p=w+bag[num].benefit;
}
*bound_u=p+bag[num].benefit;
return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) );
}
void LCbag()
{
int bound_u=0, bound_c=0;//當前結點的c限界和u限界
for(int i=0; i<number; i++)//逐層遍歷解樹決定是否裝入各個物品
{
if( ( bound_c=getbound(i+1, &bound_u) )>upbound )//遍歷左子樹
upbound=bound_u;//更改已有u限界,不更改標志
if( getbound(i, &bound_u)>bound_c )//遍歷右子樹
//若裝入，判斷右子樹的c限界是否大於左子樹根的c限界，是則裝入
{
upbound=bound_u;//更改已有u限界
curp=curp+bag[i].benefit;
curw=curw+bag[i].weight;//從已有重量和效益加上新物品
bag[i].flag=1;//標記為裝入
}
}
}
void Display()
{
cout<<"可以放入背包的物品的編號為：";
for(int i=0; i<number; i++)
if(bag[i].flag>0)
cout<<i+1<<" ";
cout<<endl;
delete []bag;
}
⑦ 關於一道C語言的背包問題，用的是貪心演算法
#include "iostream.h"
#include "stdio.h"
#include <cstdlib>
struct stone
{
int name;
int weight;//物品的剩餘重量
int weight_t;//物品的重量
float benefit;//物品的價值
//float b;
};
//按物品的效益排序
void sort(stone *data,int num)
{
//僅剩一個元素時排序完畢
if(num<1)
return;
int low=0,high=num;
stone key_s=data[low];//取數組的第一個作為關鍵字
float key=(float)key_s.benefit/key_s.weight;
int empty=low;//目標位置初始位置為low指向的位置
while(low<high)
{
if(low==empty)//後面的指針向前走
{
//找到比關鍵字小的元素把它移到low指向的位置
while((data[high].benefit/data[high].weight<key)&&(high>low))
{
high--;
}
if(data[high].benefit/data[high].weight>=key)
{
data[low]=data[high];
empty=high;
}
}
else if(high==empty)//前面的指針向後走
{
//找到比關鍵字大的元素把它移到high指向的位置
while((data[low].benefit/data[low].weight>=key)&&(low<high))
{
low++;
}
if(data[low].benefit/data[low].weight<key)
{
data[high]=data[low];
empty=low;
}
}
}
data[empty]=key_s;//把關鍵字放到劃分完畢後兩部分的中間位置
//關鍵字前面的數列繼續遞推
if(empty>1)
sort(data,empty-1);
//關鍵字後面的數列繼續遞推
if(num-empty-1>0)
sort(data+empty+1,num-empty-1);
}
//輸入物品的信息
void inputstone(stone *bag,int num)
{
for(int i=0;i<num;i++)
{
bag[i].name=i+1;//物品的名字
printf("請輸入第%d號物品的重量:",i+1);
scanf("%d",&bag[i].weight);
if (bag[i].weight<=0)
{printf("物品的重量必須大於0!\n");}
printf("請輸入第%d號物品的價值:",i+1);
scanf("%f",bag[i].benefit);
if (bag[i].benefit<=0)
{printf("物品的價值必須大於0!\n");}
bag[i].weight_t=bag[i].weight;
}
}
//主函數
int main(int argc, char* argv[])
{ int i;
int num=0;//放入物品的數量
int weight=0;//背包可容納的重量
float benefit=0;//總效益
stone *bag;//物品
/////輸入背包可容納的重量
do
{
printf("請輸入背包可容納的重量:");
scanf("%d",&weight);
if (weight<=0)
printf("背包可容納的重量必須大於0!\n");
}while(weight<=0);
//輸入物品種類
do
{
printf("請輸入物品的數量:");
scanf("%d",&num);
if (num<=0)
printf("物品數量必須大於0!\n");
}while(num<=0);
bag=new stone[num];//物品數組
inputstone(bag,num);//輸入物品的信息
sort(bag,num-1);//按單位效益排序
for(i=0;i<num&&weight>0;i++)
{
stone *temp=bag+i;
if(weight>=temp->weight)
{
weight-=temp->weight;
temp->weight=0;
benefit+=temp->benefit;
continue;
}
else
{
temp->weight-=weight;
weight=0;
benefit+=(temp->benefit*(1-(float)temp->weight/temp->weight_t));
break;
}
}
////////輸出結果//////////
printf("物品種類 放入的比例 每單位效益 ");
for(i=0;i<num;i++)
{
stone *temp=bag+i;
printf("%d類物品",temp->name);
printf("\t\t%.2f\t\t",(temp->weight_t-temp->weight)/(float)temp->weight_t);
printf(" %.4f\n",temp->benefit/(float)temp->weight_t);
}
printf("總效益:%.2f",benefit);
delete bag;
getchar();
system("PAUSE");
return EXIT_SUCCESS;
return 0;
}
⑧ 貪心演算法解決特殊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];
}
}
⑨ 急，分全拿出來了，演算法中的背包問題的貪心演算法
#include <stdio.h>
#include <iostream.h>
#define MAXWEIGHT 20
#define n 3
float pw[n]={0},x[n]={0};
int w[n]={0},p[n]={0};
void sort(int p[],int w[])
{
int temp1,temp2;
float temp;
int i,j;
for(i=0;i<n;i++)
{
pw[i]=float(p[i])/w[i];
}
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(pw[i]<pw[j])
{
temp=pw[i],pw[i]=pw[j],pw[j]=temp;
temp1=p[i],temp2=w[i];
p[i]=p[j],w[i]=w[j];
p[j]=temp1,w[j]=temp2;
}
}
}
}
void GreedyKnapsack(int p[],int w[])
{
int m=MAXWEIGHT,i;
for(i=0;i<n;i++) x[i]=0.0;
for(i=0;i<n;i++)
{
if(w[i]>m) break;
x[i]=1.0;
m=m-w[i];
}
if(i<n) x[i]=float(m)/w[i];
}
void main()
{
int i;
printf("請輸入每個物體的效益和重量:\n");
for(i=0;i<n;i++)
{
cin>>p[i]>>w[i];
}
for(i=0;i<n;i++)
{
printf("原物體%d的效益和重量分別為%d,%d:\n",i+1,p[i],w[i]);
}
sort(p,w);
printf("\n\n\n按效益值非遞增順序排列物體:\n");
for(i=0;i<n;i++)
{
printf("物體%d的效益和重量分別為%d,%d 效益值為:%f\n",(i+1),p[i],w[i],pw[i]);
}
GreedyKnapsack(p,w);
printf("\n\n\n最優解為:\n");
for(i=0;i<n;i++)
{
printf("第%d個物體要放%f:\n",i+1,x[i]);
}
}
這是正確的演算法