設有編號為1、2、......、n的n個物品,它們的重量分別為w1、w2、......、wn,價值分別為v1、v2、......、vn,其中wi和vi均為正數,有一個揹包可以懈怠的最大重量不超過W。求解目標是在不超過揹包附中的前提下使揹包裝入的總價值最大(即效益最大化)。與0/1揹包問題的區別是,這裡的每個物品可以取一部分裝入揹包。
採用貪婪法求解。用結構體儲存物品的價值、重量和價重比,在輸入價值重量後,首先求每個物品的價重比p=v/w,將所有物品按照價重比進行排序,從價重比最大的物品開始遍歷,若當前物品的重量小於揹包剩餘容量wieght,將這個物品全部放入揹包中,直到其中一個物品的重量w大於揹包剩餘容量或者物品放完,若其中一個物品的重量w大於揹包剩餘容量,就將其一部分裝入揹包,剩餘若還有物品沒裝,便置為0。
#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;
}
排序演演算法時間複雜度O(nlogn),while迴圈時間複雜度為O(n),所以本演演算法的時間複雜度為O(nlogn)。
有n個集裝箱要裝上一艘載重量為W的輪船,其中集裝箱i(1<=i<=n)的重量為wi。不考慮集裝箱的體積限制,現要儘可能多的集裝箱裝上輪船,使他們的重量之和不超過W。
題說要儘可能多的集裝箱裝上輪船,這裡採用貪婪法求解,選出儘可能多的集裝箱個數。因此,當重量限制為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即為最後輪船上的總重量。
#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;
}
快速排序時間複雜度為O(nlogn),遍歷重量時間複雜度為O(n),故本演演算法時間複雜度為O(nlogn)。
兩千多年前的戰國時期,齊威王與大將田忌賽馬。雙方約定每人各出300匹馬,並且在上、中、下三個等級中各選一匹進行比賽,由於齊威王每個等級的馬都比田忌的馬略強,比賽的結果可想而知。現在雙方各n匹馬,依次派出一匹馬進行比賽,每一輪獲勝的一方將從輸的一方得到200銀幣,平局則不用出錢,田忌已知所有馬的速度值並可以安排出場順序,問他如何安排比賽獲得的銀幣最多。輸入描述:輸入包含多個測試用例,每個測試用例的第一行正整數n(n≤1000)馬的數量,後兩行分別是n個整數,表示田忌和齊威王的馬的速度值。輸入n=0結束。輸出描述:每個測試用例輸出一行,表示田忌獲得的最多銀幣數。
採用貪婪演演算法。令田忌馬的速度陣列為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、其他情況。平局。
#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;
}
演演算法主要花費在快速排序,因此時間複雜度為O(nlogn)。
設有n個獨立的作業{1,2,......,n},由m臺相同的及其{1,2,......,m}進行加工處理,作業i所需的處理時間為ti(1<=i<=n),每個作業均可在任何一臺及其上加工處理,但未完工前不允許中斷,任何作業也不能拆分成更小的子作業。多機排程問題要求給出一種作業排程方案,使所給的n個作業在儘可能短的時間內由m臺機器加工處理完成。
採用貪婪法求解。題說要求在儘可能短的時間內完成,因此分為兩種情況,當n<=m時,機器比作業多,可以為每個作業分配一臺機器。當n>m時,作業比機器多,此時考慮長作業優先(因為短作業優先時,最開始每個機器上都是短作業,最後分配長作業會發現非常耗時),使用結構體NodeType儲存每個作業,包括no(作業編號)、t(時間)、mmo(分配的機器編號)。首先對結構體陣列A[n]按照時間從大到小進行排序,先把每個機器上分配一個作業,使用小根堆qu(小根堆會自動排序)來存放結構體,分配下一輪作業時,按照上一輪作業完成時間越小越先出隊即e=qu.top(),qu.pop()。出隊後將機器分配給下一個作業,並加上時間A[i].t,在將其新增到小根堆中,直到作業分配完畢。
#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;
}
演演算法快速排序時間複雜度O(nlogn),兩次for迴圈時間複雜度共O(n),因此本演演算法時間複雜度為O(nlogn)。
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;//按照過載後的小於規則,從大到小排序,大的優先順序高