貪婪法求解問題

2023-10-25 15:01:13

一、揹包問題

1.1 問題描述

  設有編號為1、2、......、n的n個物品,它們的重量分別為w1、w2、......、wn,價值分別為v1、v2、......、vn,其中wi和vi均為正數,有一個揹包可以懈怠的最大重量不超過W。求解目標是在不超過揹包附中的前提下使揹包裝入的總價值最大(即效益最大化)。與0/1揹包問題的區別是,這裡的每個物品可以取一部分裝入揹包。

1.2 求解思路

  採用貪婪法求解。用結構體儲存物品的價值、重量和價重比,在輸入價值重量後,首先求每個物品的價重比p=v/w,將所有物品按照價重比進行排序,從價重比最大的物品開始遍歷,若當前物品的重量小於揹包剩餘容量wieght,將這個物品全部放入揹包中,直到其中一個物品的重量w大於揹包剩餘容量或者物品放完,若其中一個物品的重量w大於揹包剩餘容量,就將其一部分裝入揹包,剩餘若還有物品沒裝,便置為0。

1.3 詳細程式碼

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXV 51

struct NodeType{
	double v;//價值
	double w;//重量
	double p;//價重比 
}; 

int n;		 //物品件數 
double W;//揹包限重 
NodeType a[MAXV]={{0}};//所有物品

double sumv=0;		 //當前揹包中物品價值
double x[MAXV]={0};//標記每件物品裝了多少進揹包 

void KNap(){
	double weight=W;//揹包剩餘重量
	int i;
	for(i=0;i<n;i++){
		if(a[i].w<weight){//從價重比最大的開始,若能直接裝入,就直接裝入 
			x[i]=1;
			weight-=a[i].w;
			sumv+=a[i].v;
		}
		else if(a[i].w>weight){//直到其中一個不能完全裝入,退出迴圈 
			break;
		}
	} 
	if(weight>0){//還能繼續裝入 
		x[i]=weight/a[i].w;			//這件物品裝入一部分 
		sumv+=x[i]*a[i].v;
	}
}

bool cmp(NodeType p1,NodeType p2){//排序 
	return p1.p>p2.p;
}

void Disp(){				//輸出 
	cout<<"W\t"<<"V\t"<<"V/W"<<endl; 
	for(int i=0;i<n;i++){
		cout<<a[i].v<<"\t"<<a[i].w<<"\t"<<a[i].p<<endl;
	}
}
void Init(){
	cout<<"請輸入物品件數:"<<endl;
	cin>>n;
	cout<<"請輸入揹包限重:"<<endl;
	cin>>W;
	cout<<"請輸入物品重量和價值:"<<endl;
	double v,w;
	for(int i=0;i<n;i++){
		cout<<"第"<<i+1<<"件物品:";
		cin>>w>>v;
		a[i].v=v;
		a[i].w=w;
		a[i].p=v/w;
	}
	cout<<"排序前:"<<endl;
	Disp(); 
	sort(a,a+n,cmp);		//排序 
	cout<<"排序後:"<<endl;
	Disp();
	KNap();
	cout<<"求解結果:"<<endl;
	cout<<"x:[ ";
	for(int i=0;i<n;i++){
		if(i==n-1) cout<<x[i];
		else cout<<x[i]<<" , ";
	}
	cout<<"]"<<endl;
	cout<<"總價值:"<<sumv<<endl;
}

int main(){
	Init();
	return 0;
}

1.4 複雜度分析

  排序演演算法時間複雜度O(nlogn),while迴圈時間複雜度為O(n),所以本演演算法的時間複雜度為O(nlogn)。

二、最優裝載問題

2.1 問題描述

  有n個集裝箱要裝上一艘載重量為W的輪船,其中集裝箱i(1<=i<=n)的重量為wi。不考慮集裝箱的體積限制,現要儘可能多的集裝箱裝上輪船,使他們的重量之和不超過W。

2.2 求解思路

  題說要儘可能多的集裝箱裝上輪船,這裡採用貪婪法求解,選出儘可能多的集裝箱個數。因此,當重量限制為W時,wi越小可裝載的集裝箱個數越多,所以採用優先選取重量輕的集裝箱裝船。對於已有的集裝箱重量陣列w[n],通過sort排序對重量按照從小到大的順序進行排序,並設定一個標記陣列x[n],標記集裝箱是否被裝入,0表示未被裝入,1表示已被裝入,船剩餘載重量weight船當前載重maxw。遍歷陣列w,當w[i]<weight時,將其裝入,設x[i]=1,weight-=w[i],maxw+=w[i]。直到集裝箱被完全裝入或剩餘集裝箱裝不進時,退出迴圈,求解完畢。maxw即為最後輪船上的總重量。

2.3 詳細程式碼

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXV 51

int w[]={0,5,2,4,3};//每個集裝箱的重量
int n=5,W=10;		// 5個集裝箱,船載重為W
int maxw=0;			//存放最優解重量
int x[MAXV]={0};	//標記物品是否被存放 

bool cmp(int a,int b){
	return a<b;
}

void solve(){
	int resw=W;
	sort(w+1,w+n+1,cmp);//對重量進行排序
	for(int i=1;i<=n&&w[i]<=resw;i++){
		maxw+=w[i];
		x[i]=1;
		resw-=w[i];
	}
}

int main(){
	solve();
	cout<<"最優方案為:"<<endl; 
	for(int i=1;i<=n;i++){
		if(x[i]==1) cout<<w[i]<<" ";
	}
	cout<<endl;
	cout<<"最優解重量為:"<<maxw<<endl;
	return 0;
}

2.4 時間複雜度分析

  快速排序時間複雜度為O(nlogn),遍歷重量時間複雜度為O(n),故本演演算法時間複雜度為O(nlogn)。

三、田忌賽馬問題

3.1 問題描述

  兩千多年前的戰國時期,齊威王與大將田忌賽馬。雙方約定每人各出300匹馬,並且在上、中、下三個等級中各選一匹進行比賽,由於齊威王每個等級的馬都比田忌的馬略強,比賽的結果可想而知。現在雙方各n匹馬,依次派出一匹馬進行比賽,每一輪獲勝的一方將從輸的一方得到200銀幣,平局則不用出錢,田忌已知所有馬的速度值並可以安排出場順序,問他如何安排比賽獲得的銀幣最多。輸入描述:輸入包含多個測試用例,每個測試用例的第一行正整數n(n≤1000)馬的數量,後兩行分別是n個整數,表示田忌和齊威王的馬的速度值。輸入n=0結束。輸出描述:每個測試用例輸出一行,表示田忌獲得的最多銀幣數。

3.2 求解思路

  採用貪婪演演算法。令田忌馬的速度陣列為t[n],左右兩側分別為leftt、rightt,齊威王馬的速度陣列為q[n],左右兩側分別為leftq,rightq。田忌獲得的銀幣即為monry。田忌賽馬問題可以分為以下幾種情況:
(1)田忌最快的馬比齊威王最快的馬快。此時最優解就是兩者比賽,田忌贏。此時rightt--,rightq--,money+=200;
(2)田忌最快的馬比齊威王最快的馬慢。此時最優解是用田忌最慢的馬與齊威王最快的馬比賽,田忌輸。此時leftt++,rightq--,money-=200;
(3)田忌最快的馬和齊威王最快的馬一樣快。此時又分為以下三種情況:
  1、田忌最慢的馬比齊威王最慢的馬快。此時最優解就是兩者比賽,田忌贏。此時leftt++,leftq++,money+=200;
  2、田忌最慢的馬比齊威王最慢的馬慢。此時最優解就是用田忌最慢的馬與齊威王最快的馬比賽,田忌輸。此時leftt++,rightq--,money-=200;
  3、其他情況。平局。

3.3 詳細程式碼

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXV 1001

int n;			//馬總數
int t[MAXV];	//田忌 
int q[MAXV];	//齊威王
int money=0;	//田忌獲得的銀幣總數 

void solve(){
	sort(t,t+n);//將馬的速度按從小到大排序 
	sort(q,q+n);
	int leftt=0;
	int leftq=0;
	int rightt=n-1;
	int rightq=n-1;
	while(leftt<=rightt){
		if(t[rightt]>q[rightq]){//田忌最快的馬齊威王最快的馬快,田忌贏 
			money+=200;
			rightt--;
			rightq--;
		}
		else if(t[rightt]<q[rightq]){//田忌最快的馬比齊威王最快的馬慢 
			money-=200;
			leftt++;			//最優解為田忌用最慢的馬與齊威王比,田忌輸 
			rightq--;
		}
		else {					////田忌最快的馬與齊威王最快的馬速度相同 
			if(t[leftt]>q[leftq]){//田忌最慢的馬比齊威王最慢的馬快,田忌贏 
				money+=200;
				leftt++;
				leftq++;
			}
			else if(t[leftt]<q[leftq]){//田忌最慢的馬比齊威王最慢的馬慢 
				money-=200;
				leftt++;		//最優解為田忌最慢的馬與齊威王最快的馬比,田忌輸 
				rightq--;
			}
		}
	}
}

int main(){
	while(true){
		cout<<"請輸入馬的總數:";
		cin>>n;
		if(n==0) return 0;
		cout<<"請輸入田忌各匹馬的速度:"<<endl;
		for(int i=0;i<n;i++){
			cin>>t[i];
		}
		cout<<"請輸入齊威王各匹馬的速度:"<<endl;
		for(int i=0;i<n;i++){
			cin>>q[i];
		}
		solve();
		cout<<"田忌能獲得的銀幣最多為:"<<money;
	}
	return 0;
} 

3.4 時間複雜度分析

  演演算法主要花費在快速排序,因此時間複雜度為O(nlogn)。

四、多機排程問題

4.1 問題描述

  設有n個獨立的作業{1,2,......,n},由m臺相同的及其{1,2,......,m}進行加工處理,作業i所需的處理時間為ti(1<=i<=n),每個作業均可在任何一臺及其上加工處理,但未完工前不允許中斷,任何作業也不能拆分成更小的子作業。多機排程問題要求給出一種作業排程方案,使所給的n個作業在儘可能短的時間內由m臺機器加工處理完成。

4.2 問題求解

  採用貪婪法求解。題說要求在儘可能短的時間內完成,因此分為兩種情況,當n<=m時,機器比作業多,可以為每個作業分配一臺機器。當n>m時,作業比機器多,此時考慮長作業優先(因為短作業優先時,最開始每個機器上都是短作業,最後分配長作業會發現非常耗時),使用結構體NodeType儲存每個作業,包括no(作業編號)、t(時間)、mmo(分配的機器編號)。首先對結構體陣列A[n]按照時間從大到小進行排序,先把每個機器上分配一個作業,使用小根堆qu(小根堆會自動排序)來存放結構體,分配下一輪作業時,按照上一輪作業完成時間越小越先出隊即e=qu.top(),qu.pop()。出隊後將機器分配給下一個作業,並加上時間A[i].t,在將其新增到小根堆中,直到作業分配完畢。

4.3 詳細程式碼

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

int n=7;	//n個作業
int m=3;	//m個機器 
struct NodeType{
	int no;//作業序號
	int t;//作業時長
	int mmo;//機器序號
	bool operator < (const NodeType& s) const{//按t從大到小排序 
		return t>s.t;
	} 
};
NodeType A[]={{1,2},{2,14},{3,4},{4,16},{5,6},{6,5},{7,3}}; 

void solve(){
	NodeType e;
	if(n<=m){
		cout<<"為每一個作業分配一臺機器"<<endl;
		return ;
	}
	sort(A,A+n);
	priority_queue<NodeType,vector<NodeType>,less<NodeType> > qu;//小根堆,小的元素在上面(自動排序) 
	for(int i=0;i<m;i++){
		A[i].mmo=i+1;
		cout<<"給機器"<<i+1<<"分配作業"<<A[i].no<<",執行時間為"<<A[i].t<<",佔用時間段[0,"<<A[i].t<<"]"<<endl;
		qu.push(A[i]);
	}
	for(int i=m;i<n;i++){
		e=qu.top();
		qu.pop();
		cout<<"給機器"<<e.mmo<<"分配作業"<<A[i].no<<",執行時間為"<<A[i].t<<",佔用時間段["<<e.t<<","<<e.t+A[i].t<<"]"<<endl;
		e.t+=A[i].t; 
		qu.push(e);
	}
}

int main(){
	cout<<"多機排程問題:"<<endl;
	solve();
	return 0;
}

4.4 時間複雜度分析

  演演算法快速排序時間複雜度O(nlogn),兩次for迴圈時間複雜度共O(n),因此本演演算法時間複雜度為O(nlogn)。

4.5 小根堆(之前對小根堆了解不多下面記錄一下堆)

1、大根堆:是完全二元樹,其中根結點大於子節點;小根堆:是完全二元樹,其中根結點小於子節點。
2、c++中,小根堆和大根堆可以使用優先佇列實現(priority_queue),優先順序高的先出隊,自動排序。

#include<queue>
priority_queue<int> qu;//預設是大根堆
priority_queue<int,vector<int>,greater<int> > qu;//小根堆
priority_queue<int,vector<int>,less<int> > qu;//大根堆

在使用結構體時

#include<queue>
struct Node{
  int x,y;
  bool operator < (const Node& a)const{//小的先進堆
    return x<a.x;
  }
};
priority_queue<Node,vector<Node>,less<Node> > qu;//按照過載後的小於規則,從大到小排序,大的優先順序高