貪心演算法歷史背景_關於編程的書籍

『壹』關於編程的書籍

一、Python系列（3本）

如果你之前一點編程經驗都沒有，先看如下兩本：

1、《簡明Python教程》(A Byte of Python)

入門Python的絕佳Tutorial，從書的目錄便可以了解到作者Swaroop C H清晰的行文思路，以及對Python高超的駕馭能力。

2、《集體智慧編程》

以具體實例的方式來展示Python的編程技巧，受益良多。作者用非常直觀的方式向讀者展示了人工智慧和機器學習中的大量經典的演算法。更可貴的是，作者在展示演算法時所使用的例子都是網路中非常有代表性的場景，並且很多情況下還會結合一些實際運營的 Web 站點的數據作更進步闡釋。當然，作為一本實用型的書，少不了的是大量可運行的代碼。

3、《Python Cookbook中文版，第3版》

這本書可謂Python版《代碼大全》。有人說《代碼大全》這類書是字典，其實不盡然《代碼大全》是高手過招。《Cookbook》也如此，閱讀時總能讓你有一種：「哇塞，漂亮！」的感覺。能把 Cookbook 全部讀完，你的Python水平絕對發生質變。

二、Java語言系列（3本）

1、《Java核心技術·卷1：基礎知識（原書第9版）》

Java領域最有影響力和價值的著作之一，擁有20多年教學與研究經驗的資深Java技術專家撰寫，與《Java編程思想》齊名。

2、《演算法第四版》

Java 語言描述，演算法領域經典的參考書，全面介紹了關於演算法和數據結構的必備知識，並特別針對排序、搜索、圖處理和字元串處理進行了論述。書的內容非常多，可以說是Java程序員的必備書籍之一

3、《數據結構與演算法分析：Java語言描述》

這本書真是非常好！個人感覺很適合給初學者入門看，裡面的分析數學公式恰到好處，沒有演算法導論的令人望而生畏，也沒有國內圖書的草草了事，既學習了數據結構又有剛剛好的演算法分析，很容易使人產生共鳴。

當然，對於Java我們建議進行系統的學習，扎實基礎不能只靠看書。如果你有任何疑問，歡迎你在千鋒武漢官網上留下你的相關情況，我再對號入座幫你解答。
在這里插入圖片描述
三、前端系列（4本）

1、《Java權威指南（第6版）》

淘寶前端團隊翻譯，這本書又叫犀牛書，號稱Java開發者的聖經，網上對此書評價很多，大概意思都是說這本書是一本Java文檔手冊，沒有完整看過一遍此書的都不能算是一名合格的前端工程師。

2、《Java高級程序設計（第3版）》

又稱紅寶書，雅虎首席前端架構師，YUI的作者Zakas出品。雖然書名帶了「高級」二字，但是講得也很基礎，而且行文風格很流暢，每一小節就像是一篇博客，讀起來並不枯燥，個人感覺比上面那本犀牛書可讀性更強。

3、《Java設計模式與開發實踐》

本書是在設計模式上的進一步擴充。一大特點就是結合實操，代碼完整能直接應用到實際開發中。

4、《Web性能權威指南》

本書是谷歌公司高性能團隊核心成員的權威之作，堪稱實戰經驗與規范解讀完美結合的產物。本書目標是涵蓋Web開發者技術體系中應該掌握的所有網路及性能優化知識。

『貳』求解一貪心演算法問題

最快回答那個不懂別亂說，別誤人子弟。
這題標準的貪心演算法，甚至很多時候被當做貪心例題
要求平均等待時間，那麼就得用總等待時間 / 人數
所以只用關心總等待時間，
如果數據大的在前面，那麼後面必然都要加一次這個時間，所以按從小到大排。
給你寫了個，自己看吧。
#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
int n;
float arr[105];
cin >> n;
for(int i = 0; i < n; ++i)
cin >> arr[i];
sort(arr, arr+n);
int tnow = 0;
int tmax = 0;
for(int i = 0; i < n; ++i)
{
tmax += tnow;
tnow += arr[i];
}
for(int i = 0; i < n; ++i)
{
printf("%0.2f ", arr[i]);
}
cout << endl;
printf("%0.2f\n",tmax / (float)n);
return 0;
}

『叄』 C++貪心演算法排座位問題

noip2008的題嗎？排序加貪心就行了

『肆』應用問題求解，加油站有效加油位問題！

1.已知有
3
個物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容積
M=20，根據
0-1
背
包動態規劃的遞推式求出最優解。
2.按要求完成以下關於排序和查找的問題。
①對數組
A={15，29，135，18，32，1，27，25，5}，用快速排序方法將其排成遞減序。
②請描述遞減數組進行二分搜索的基本思想，並給出非遞歸演算法。
③給出上述演算法的遞歸演算法。
④使用上述演算法對①所得到的結果搜索如下元素，並給出搜索過程：18，31，135。
3.已知
1
(
)
*
(
)
i
i
k
k
ij
r
r
A
a
+
=
，
k
=1，2，3，4，5，6，
r
1
=5，
r
2
=10，
r
3
=3，
r
4
=12，
r
5
=5，
r
6
=50，
r
7
=6，
求矩陣鏈積
A
1
×A
2
×A
3
×A
4
×A
5
×A
6
的最佳求積順序（要求給出計算步驟）
。
4.
根
據
分
枝
限
界
算
法
基
本
過
程
,
求
解
0-1
背
包
問
題
。
已
知
n=3,M=20
，
(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。
5.試用貪心演算法求解汽車加油問題：
已知一輛汽車加滿油後可行駛
n
公里，
而旅途中有若干個加油站。
試設計一個有效演算法，指出應在哪些加油站停靠加油，使加油次數最少，請寫出該演算法。
6.試用動態規劃演算法實現下列問題：設
A
和
B
是兩個字元串。我們要用最少的字元操作，將字元串
A
轉換為字元串
B，這里所說的字元操作包括：
①刪除一個字元。
②插入一個字元。
③將一個字元改為另一個字元。
請寫出該演算法。
7.對於下圖使用
Dijkstra
演算法求由頂點
a
到頂點
h
的最短路徑。
8.試寫出用分治法對數組
A[n]實現快速排序的演算法。
9.有
n
個活動爭用一個活動室。
已知活動
i
佔用的時間區域為[s
i
，
f
i
]，
活動
i,j
相容的條件是：
sj≥f
i
，問題的解表示為(x
i
|
x
i
=1，2…，n,)，x
i
表示順序為
i
的活動編號活動，求一個相容的活動子
集，且安排的活動數目最多。
10.設
x
1
、
x
2
、
x
3
是一個三角形的三條邊，而且
x
1
+x
2
+x
3
=14。請問有多少種不同的三角形？給出解答過
程。
11.設數組
A
有
n
個元素，需要找出其中的最大最小值。
①請給出一個解決方法，並分析其復雜性。
②把
n
個元素等分為兩組
A1
和
A2，分別求這兩組的最大值和最小值，然後分別將這兩組的最大值
和最小值相比較，求出全部元素的最大值和最小值。如果
A1
和
A2
中的元素多於兩個，則再用上述
方法各分為兩個子集。直至子集中元素至多兩個元素為止。這是什麼方法的思想？請給出該方法的
演算法描述，並分析其復雜性。
12.有
n
個程序和長度為
L
的磁帶，
程序
i
的長度為
a
i
，
已知
L
a
n
i
i
≻
∑
=
1
，
求最優解(x
i
，
x
2
，
...，
x
i
，
…，
x
n
)，x
i
=0，1,
x
i
=1，表示程序
i
存入磁帶，x
i
=0，表示程序
i
不存入磁帶，滿足
L
a
x
n
i
i
i
≤
∑
=
1
，
且存放的程序數目最多。
13.試用分治法實現有重復元素的排列問題：設
)
,...,
,
{
2
1
n
r
r
r
R
=
是要進行排列的
n
個元素，其中元素
n
r
r
r
,...,
,
2
1
可能相同，試設計計算
R
的所有不同排列的演算法。
14.試用動態規劃演算法實現
0-1
閉包問題，請寫出該演算法。
15.試用貪心演算法求解下列問題：將正整數
n
分解為若干個互不相同的自然數之和，使這些自然數的乘
積最大，請寫出該演算法。
16.試寫出用分治法對一個有序表實現二分搜索的演算法。
17.試用動態規劃演算法實現最長公共子序列問題，請寫出該演算法。
18.假設有
7
個物品，它們的重量和價值如下表所示。若這些物品均不能被分割，且背包容量
M＝150，
使用回溯方法求解此背包問題，請寫出狀態空間搜索樹。
物品
A
B
C
D
E
F
G
重量
35
30
60
50
40
10
25
價值
10
40
30
50
35
40
30
19.求解子集和問題：對於集合
S={1，2
，6，8}，求子集，要求該子集的元素之和
d=9。
①畫出子集和問題的解空間樹；
②該樹運用回溯演算法，寫出依回溯演算法遍歷節點的順序；
③如果
S
中有
n
個元素，指定
d，用偽代碼描述求解子集和問題的回溯演算法。
20.求解填字游戲問題：在
3×3
個方格的方陣中要填入數字
1
到
N（N≥10）內的某
9
個數字，每個方
格填一個整數，似的所有相鄰兩個方格內的兩個整數之和為質數。試採用回溯法寫出滿足這個要求
的一種數字填法的演算法和滿足這個要求的全部數字填法的演算法。
21.試用動態規劃演算法實現最大子矩陣和問題：
求
n
m
×
矩陣
A
的一個子矩陣，
使其各元素之和為最大。
22.試用回溯法解決下列整數變換問題：關於整數
i
的變換
f
和
g
定義如下：
⎣
⎦
2
/
)
(
;
3
)
(
i
i
g
i
i
f
=
=
。
對於給定的兩個整數
n
和
m
，要求用最少的變換
f
和
g
變換次數將
n
變為
m
。
23.關於
15
謎問題。在一個
4×4
的方格的棋盤上，將數字
1
到
15
代表的
15
個棋子以任意的順序置入
各方格中，空出一格。要求通過有限次的移動，把一個給定的初始狀態變成目標狀態。移動的規則
是：每次只能把空格周圍的四格數字（棋子）中的任意一個移入空格，從而形成一個新的狀態。為
了有效的移動，設計了估值函數
C
1
(x)，表示在結點
x
的狀態下，沒有到達目標狀態下的正確位置
的棋子的個數。

『伍』很簡單的C語言貪心演算法，用map做的，但我對map有個問題

改成 pw.insert(make_pair(5,10));

『陸』 id3演算法是什麼

ID3演算法是一種貪心演算法，用來構造決策樹。ID3演算法起源於概念學習系統（CLS），以信息熵的下降速度為選取測試屬性的標准，即在每個節點選取還尚未被用來劃分的具有最高信息增益的屬性作為劃分標准，然後繼續這個過程，直到生成的決策樹能完美分類訓練樣例。

ID3演算法的背景

ID3演算法最早是由羅斯昆（J. Ross Quinlan）於1975年在悉尼大學提出的一種分類預測演算法，演算法的核心是「信息熵」。ID3演算法通過計算每個屬性的信息增益，認為信息增益高的是好屬性，每次劃分選取信息增益最高的屬性為劃分標准，重復這個過程，直至生成一個能完美分類訓練樣例的決策樹。

『柒』證明題：用解背包問題的貪心演算法解0-1背包問題時不一定得到最優解急求！！

貪心演算法總是作出在當前看來是最好的選擇，即貪心演算法並不從整體最優解上加以考慮，它所作出的選擇只是在某種意義上的局部最優解。
背包問題可以用貪心演算法求解，而0-1背包問題卻不能用貪心演算法求解。
用貪心演算法求解背包問題的步驟是，首先計算每種物品單位重量的價值vi/wi；然
後，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包後，背包內的物品總量未超過c，則選擇單位重量價值次高的物
品並盡可能多地裝入背包。依此策略一直進行下去，直到背包裝滿為止。
在最後一步包裝不下時可能會分割物品，而0-1背包問題不能分割物品，故不一定得到最優解。
取一反例即可說明

『捌』大學排課需要注意什麼

1課題背景與研究意義
排課問題早在70年代就證明是一個NP完全問題，即演算法的計算時間是呈指數增長的，這一論斷確立了排課問題的理論深度。對於NP問題完全問題目前在數學上是沒有一個通用的演算法能夠很好地解決。然而很多NP完全問題目具有很重要的實際意義，例如。大家熟悉地路由演算法就是很典型的一個NP完全問題，路由要在從多的節點中找出最短路徑完成信息的傳遞。既然都是NP完全問題，那麼很多路由演算法就可以運用到解決排課問題上，如Dijkstra演算法、節點子樹剪枝構造網路最短路徑法等等。
目前大家對NP 完全問題研究的主要思想是如何降低其計算復雜度。即利用一個近似演算法來代替，力爭使得解決問題的時間從指數增長化簡到多項式增長。結合到課表問題就是建立一個合適的現實簡約模型，利用該簡約模型能夠大大降低演算法的復雜度，便於程序實現，這是解決排課問題一個很多的思路。
在高等院校中，培養學生的主要途徑是教學。在教學活動中，有一系列管理工作，其中，教學計劃的實施是一個重要的教學環節。每學期管理人員都要整理教學計劃，根據教學計劃下達教學任務書，然後根據教學任務書編排課程表。在這些教學調度工作中，既有大量繁瑣的數據整理工作，更有嚴謹思維的腦力勞動，還要填寫大量的表格。因此工作非常繁重。
加之，隨著教學改革的進行及「211」工程的實施，新的教育體制對課表的編排提出了更高的要求。手工排課時，信息的上通下達是極其麻煩的，而採用計算機排課，教學中的信息可以一目瞭然，對於優化學生的學習進程，評估每位教師對教學的貢獻，領導合理決策等都具有重要的意義，必將會大大推進教學的良性循環。
2課題的應用領域
本課題的研究對開發高校排課系統有指導作用。
排課問題的核心為多維資源的沖突與搶占，對其研究對類似的問題（特別是與時間表有關的問題：如考試排考場問題、電影院排座問題、航空航線問題）也是個參考。
3 課題的現狀
年代末，國外就有人開始研究課表編排問題。1962年，Gotlieb曾提出了一個課表問題的數學模型，並利用匈牙利演算法解決了三維線性運輸問題。次後，人們對課表問題的演算法、解的存在性等問題做了很多深入探討。但是大多數文獻所用的數學模型都是Gotlieb的數學模型的簡化或補充，而至今還沒有一個可行的演算法來解決課表問題。
近40年來，人們對課表問題的計算機解法做了許多嘗試。其中，課表編排的整數規劃模型將問題歸結為求一組0-1變數的解，但是其計算量非常大。解決0-1線性優化問題的分支一定界技術卻只適用也規模較小的課表編排，Mihoc和Balas（1965）將課表公式化為一個優化問題，Krawczk則提出一種線性編程的方法。Junginger將課表問題簡化為三維運輸問題，而Tripathy則把課表問題視作整數線性編程問題並提出了大學課表的數學模型。
此外，有些文獻試圖從圖論的角度來求解排課表的問題，但是圖的染色問題也是NP完全問題，只有在極為簡單的情況下才可以將課表編排轉化為二部圖匹配問題，這樣的數學模型與實際相差太遠，所以對於大多數學校的課表編排問題來說沒有實用價值。
進入九十年代以後，國外對課表問題的研究仍然十分活躍。比較有代表的有印度的Vastapur大學管理學院的ArabindaTripathy、加拿大Montreal大學的Jean Aubin和Jacques Ferland等。目前，解決課表方法的問題有：模擬手工排課法，圖論方法，拉格朗日法，二次分配型法等多種方法。由於課表約束復雜，用數學方法進行描述時往往導致問題規模劇烈增大，這已經成為應用數學編程解決課表問題的巨大障礙。國外的研究表明，解決大規模課表編排問題單純靠數學方法是行不通的，而利用運籌學中分層規劃的思想將問題分解，將是一個有希望得到成功的辦法。
在國內，對課表問題的研究開始於80年代初期、具有代表性的有：南京工學院的UTSS（A University Timetable Scheling System）系統，清華大學的TISER（Timetable SchelER）系統，大連理工大學的智能教學組織管理與課程調度等，這些系統大多數都是模擬手工排課過程，以「班」為單位，運用啟發式函數來進行編排的。但是這些系統課表編排系統往往比較依賴於各個學校的教學體制，不宜進行大量推廣。
從實際使用的情況來看，國內外研製開發的這些軟體系統在實用性上仍不盡如人意。一方面原因是作為一個很復雜的系統，排課要想面面俱到是一件很困難的事；另一方面每個學校由於其各自的特殊性，自動排課軟體很難普遍實用，特別是在調度的過程中一個很小的變動，要引起全部課程的大調整，這意味著全校課程大變動，在實際的應用中這是很難實現的事。
4解決NP問題的幾種演算法及其比較
解決NP完全問題只能依靠近似演算法，所以下面介紹幾種常用演算法的設計思想，包括動態規劃、貪心演算法、回溯法等。
動態規劃法是將求解的問題一層一層地分解成一級一級、規模逐步縮小的子問題，直到可以直接求出其解的子問題為止。分解成的所有子問題按層次關系構成一顆子問題樹。樹根是原問題。原問題的解依賴於子問題樹中所有子問題的解。動態規劃演算法通常用於求一個問題在某種意義下的最優解。設計一個動態規劃演算法，通常可按以下幾個步驟進行：
1. 分析最優解的性質，並刻劃其結構特徵。
2. 遞歸的定義最優解。
3. 以自底向上的方式計算出最優解。
4. 根據計算最優解時得到的信息，構造一個最優解。
步驟1~3是動態規劃演算法的基本步驟。在只需要求出最優解的情形，步驟4可以省去。若需要求出問題的一個最優解，則必須執行步驟4。此時，在步驟3中計算最優解時，通常需記錄更多的信息，以便在步驟4中，根據所記錄的信息，快速地構造出一個最優解。
（二）貪心演算法
當一個問題具有最優子結構性質時，我們會想到用動態規劃法去解它，但有時會有更簡單、更有效的演算法，即貪心演算法。顧名思義，貪心演算法總是做出在當前看來最好的選擇。也就是說貪心演算法並不是整體最優上加以考慮，他所作出的選擇只是在某種意義上的局部最優的選擇。雖然貪心演算法不是對所有問題都能得到整體最優解，但對范圍相當廣的許多問題它能產生整體最優解，如圖的演算法中單源最短路徑問題，最小支撐樹問題等。在一些情況下，即使貪心演算法不能得到整體最優解，但其最終結果卻是最優解的很好的近似解。
在貪心演算法中較為有名的演算法是Dijkstra演算法。它作為路由演算法用來尋求兩個節點間的最短路徑。Dijkstra演算法的思想是：假若G有n個頂點，於是我們總共需要求出n-1條最短路徑，求解的方法是：初試，寫出V0(始頂點)到各頂點(終頂點)的路徑長度，或有路徑，則令路徑的長度為邊上的權值；或無路經，則令為∞。再按長度的遞增順序生成每條最短路徑。事實上生成最短路徑的過程就是不斷地在始頂點V何終頂點W間加入中間點的過程，因為在每生成了一條最短路徑後，就有一個該路徑的終頂點U，那麼那些還未生成最短路徑的路徑就會由於經過U而比原來的路徑短，於是就讓它經過U。
（三）回溯法
回溯法有「通用的解題法」之稱。用它可以求出問題的所有解或任一解。概括地說，回溯法是一個既帶有系統性又帶有跳躍性的搜索法。它在包含問題所有解的一顆狀態空間樹上，按照深度優先的策略，從根出發進行搜索。搜索每到達狀態空間樹的一個節點，總是先判斷以該節點為根的子樹是否肯定不包含問題的解。如果肯定不包含，則跳過對該子樹的系統搜索，一層一層地向它的祖先節點繼續搜索，直到遇到一個還有未被搜索過的兒子的節點，才轉向該節點的一個未曾搜索過的兒子節點繼續搜索；否則，進入子樹，繼續按深度優先的策略進行搜索。

『玖』排課專家演算法是用來做什麼的

『拾』求解一道貪心演算法

因為這個問題涉及到高維求解（大於3維），所以不推薦你用貪心演算法或遺傳演算法之類的演算法。這里給出一種升級的蒙特卡羅演算法——自適應序貫數論演算法，這是一種以GLP集合為基礎的隨機遍歷演算法，可以很輕易的解決一系列的高維求解問題，目前根據網上能找到的資料最多可以做到18維。

下面就根據你給出的例子講解一下：

對於6000的料來說

1185最多做到5根（要求4根，所以一根木料對於1185的產品來說最多有0到45種可能）；1079最多做到5根；985最多做到6根；756最多做到7根。

所以第一次加工一根木料最多有5*6*7*8=1680種加工可能（當然其中包括那些產品總長度大於料長的可能，但是我們可以通過罰函數來避免這些情況），那麼利用GLP演算法我們可以一次性產生這1680種可能，然後逐個比較那種可能最省木料；

設第一加工出的產品量分別為1 1 3 1

那麼1185加工量剩3，1079剩5，985剩7，756剩7，所以第二次加工的可能性有（3+1）*（5+1）*（6+1）*（7+1）=1120種

關於自適應序貫數論演算法，根據這道題你可以這樣理解，4種尺寸構成了一個4維的空間，四種尺寸的每一種組合相當於空間中的一個點（1185的1根，1079的1根，985的3根，756的1根，這就組成了這個4維空間中的(1,1,3,1)點) ，自適應序貫數論演算法就是先根據GLP演算法在這個4維空間中隨機的，均勻的分布一定的點（也就是尺寸的組合），然後根據目標函數確定其中哪一個點是最優點，我們認為最優點的附近出現最優解的可能性最大，那麼我們就以最優點為中心，以一定的尺度為半徑將原空間縮小，然後我們在心空間中再一次利用GLP演算法均勻，隨機的充滿這個空間，然後重復以上過程，直到這個空間小到我們事先規定的大小，這樣我們就找到了最優解。

也許你會擔心演算法一上來就收斂到了局部最優解，然後一直在這里打轉，不用擔心，GLP最大的優點就是均勻的充斥整個空間，盡量將每一種可能都遍歷到。

這種演算法的缺點在於充斥空間用的點需要生成向量來生成，每一種充斥方式都需要不同的向量，你可以在《數論方法在統計中的應用》這本書中查到已有的每種充斥方式對應的那些生成向量。

下面是我跟據對你給出的例子的理解算出的結果。

1185:1根
1079:1根
985:3根
756:1根
剩餘木料0

1185:1根
1079:1根
985:3根
756:1根
剩餘木料0

1185:1根
1079:1根
985:3根
756:1根
剩餘木料0

1185:1根
1079:0根
985:1根
756:5根
剩餘木料15

1185:0根
1079:3根
985:0根
756:0根
剩餘木料2748

用去木料：5根
請按任意鍵繼續. . .

程序代碼如下：（變數都是用漢語拼音標的）

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <iostream.h>
#include <iomanip.h>
#include <time.h>
#include <fstream.h>
#include <windows.h>
#include "glp.h"
#define jiedeweishu 4
#define glpgeshu 10007
#define glpgeshu1 5003//100063
#define glpgeshu2 6007//33139//71053//172155//100063
#define yuanmuchang 6000
#define qiegesushi 5
#define chicun1 1185
#define chicun2 1079
#define chicun3 985
#define chicun4 756
#define chicun1shuliang 4
#define chicun2shuliang 6
#define chicun3shuliang 10
#define chicun4shuliang 8

float xuqiuchicun[jiedeweishu]={chicun1,chicun2,chicun3,chicun4};
float chicunxuqiuliang[jiedeweishu]={chicun1shuliang,chicun2shuliang,chicun3shuliang,chicun4shuliang};
float zuobianjie0[jiedeweishu];//{-19,1,-11,1.5,0,200};//{0.39111,-18.5,1,-11,1,0,2};//左邊界
float youbianjie0[jiedeweishu];//{-17,1.5,-7,2,0.05,900};//{0.393,-17,2,-9,2,0.1,6};//右邊界
float zuobianjie[jiedeweishu];
float youbianjie[jiedeweishu];
float zuobianjie1[jiedeweishu];//過度用
float youbianjie1[jiedeweishu];
float zuobianjie2[jiedeweishu];//局部邊界
float youbianjie2[jiedeweishu];
float zuobianjie3[jiedeweishu];//大邊界
float youbianjie3[jiedeweishu];
float sheng_cheng_xiang_liang[jiedeweishu]={1,1206,3421,2842};//生成向量
float sheng_cheng_xiang_liang1[jiedeweishu]={1,792,1889,191};//{1,39040,62047,89839,6347,30892,64404};//生成向量
float sheng_cheng_xiang_liang2[jiedeweishu]={1,1351,5080,3086};//{1,18236,1831,19143,5522,22910};//{1,18010,3155,50203,6065,13328};//{1,167459,153499,130657,99554,61040,18165};

struct chushi
{
float geti[jiedeweishu];
float shiying;
};

chushi *zuiyougeti;//精英保存策略
chushi *zuiyougetijicunqi;

int sishewuru(float);
float cha;//左右邊界的差
int biao;//判斷尋優是否成功1表示成功0表示不成功
int maxgen;//最大計算代數
int gen;//目前代數
void initialize();//演算法初始化
void jingyingbaoliu();//精英保存的實現
void mubiaohanshu1(chushi &bianliang);//適應度的計算使用殘差法
int cmpshiyingjiang(const void *p1,const void *p2)
{
float i=((chushi *)p1)->shiying;
float j=((chushi *)p2)->shiying;
return i<j ? 1:(i==j ? 0:-1);//現在是按降序牌排列，將1和-1互換後就是按升序排列
}

int cmp1(const void *p1,const void *p2)
{
float i= *(float*)p1;
float j= *(float*)p2;
return i<j ? 1:(i==j ? 0:-1);//現在是按降序牌排列，將1和-1互換後就是按升序排列
}
void main()
{
float bianjiebianhuashuzu[jiedeweishu];
float yiwanchengshuliang[jiedeweishu];
zuiyougeti=new chushi;//最優個體的生成
zuiyougetijicunqi=new chushi;

int i;

for(i=0;i<jiedeweishu;i++)
{
zuiyougeti->geti[i]=0;
yiwanchengshuliang[i]=0;
}
int muliaoshuliang=0;
while(1)
{

if(yiwanchengshuliang[0]==chicun1shuliang&&yiwanchengshuliang[1]==chicun2shuliang&&yiwanchengshuliang[2]==chicun3shuliang&&yiwanchengshuliang[3]==chicun4shuliang)
break;//都加工完了就退出程序
biao=1;

for(i=0;i<jiedeweishu;i++)
{
bianjiebianhuashuzu[i]=chicunxuqiuliang[i]-yiwanchengshuliang[i];
}
for(i=0;i<jiedeweishu;i++)
{
zuobianjie0[i]=0;
if(bianjiebianhuashuzu[i]>(int)(yuanmuchang/xuqiuchicun[i]))
{
youbianjie0[i]=(int)(yuanmuchang/xuqiuchicun[i]);
}
else
{
youbianjie0[i]=bianjiebianhuashuzu[i];
}
}
for(i=0;i<jiedeweishu;i++)
{
zuobianjie[i]=zuobianjie0[i];
youbianjie[i]=youbianjie0[i];
}
for(i=0;i<jiedeweishu;i++)//在這套程序中邊界分為兩個部分,其中一組是根據最優解的收斂范圍進行局部尋優,如果在局部找不到最優解則以現有最優解為中心進行全局搜索
{
zuobianjie2[i]=zuobianjie[i];
youbianjie2[i]=youbianjie[i];
zuobianjie3[i]=zuobianjie[i];
youbianjie3[i]=youbianjie[i];
}
zuiyougeti->shiying=-3000;
//cout<< zuiyougeti->shiying<<endl;
initialize();
//for(i=0;i<jiedeweishu;i++)/////
//{////
// cout<<zuiyougeti->geti[i]<<",";////
//}/////////
//cout<<endl;/////
// cout<<"初始最優解："<<" "<<-zuiyougeti->shiying<<endl;/////////////
for(gen=1;gen<maxgen;gen++)
{
jingyingbaoliu();
if(cha<1e-1)
break;
}
//cout<<"最終在收斂的范圍內左右邊界的最大差值: "<<cha<<endl;
//for(i=0;i<jiedeweishu;i++)
//{
// cout<<setiosflags(ios::fixed)<<setprecision(6)<<zuiyougeti->geti[i]<<",";
// }
//cout<<endl;

//cout<<"共用代數"<<gen<<endl;
cout<<"1185:"<<zuiyougeti->geti[0]<<"根"<<endl;
cout<<"1079:"<<zuiyougeti->geti[1]<<"根"<<endl;
cout<<"985:"<<zuiyougeti->geti[2]<<"根"<<endl;
cout<<"756:"<<zuiyougeti->geti[3]<<"根"<<endl;
cout<<"剩餘木料"<<(-zuiyougeti->shiying)<<endl;////////////////
cout<<endl;
for(i=0;i<jiedeweishu;i++)
{
yiwanchengshuliang[i]=yiwanchengshuliang[i]+zuiyougeti->geti[i];
}
muliaoshuliang++;

}
cout<<"用去木料："<<muliaoshuliang<<"根"<<endl;
delete [] zuiyougetijicunqi;
delete [] zuiyougeti;

system("pause");
}
void initialize()
{
maxgen=20;//最大代數
gen=0;//起始代
cha=100;
chushi *chushizhongqunji;
chushizhongqunji=new chushi[glpgeshu];
int i,j;
for(i=0;i<jiedeweishu;i++)
{
zuobianjie1[i]=zuobianjie[i];
youbianjie1[i]=youbianjie[i];
}
float **glp_shu_zu;//第一次求解，為了使解更精確這一次求解需要的點最多
glp_shu_zu=new (float *[glpgeshu]);
for(i=0;i<glpgeshu;i++)
{
glp_shu_zu[i]=new float[jiedeweishu];//生成的glp向量用glp_shu_zu儲存
}
glp glp_qiu_jie_first(glpgeshu,jiedeweishu);//定義生成多少組glp向量和向量的維數
glp_qiu_jie_first.glp_qiu_jie(glp_shu_zu,sheng_cheng_xiang_liang);//將生成的glp向量用glp_shu_zu儲存，同時將生成向量帶入glp類
for(i=0;i<glpgeshu;i++)//產生初始種群
{
for(j=0;j<jiedeweishu;j++)
{
chushizhongqunji[i].geti[j]=sishewuru((zuobianjie[j]+(youbianjie[j]-(zuobianjie[j]))*glp_shu_zu[i][j]));
if(j==3&&glp_shu_zu[i][j]<0)
{
cout<<"274"<<endl;/////////////
cout<<zuobianjie[j]<<" "<<glp_shu_zu[i][j]<<" "<<youbianjie[j]<<endl;////////////////////
system("pause");///////////////////
}
}
}
for(i=0;i<glpgeshu;i++)//計算初始種群的適應度
{
mubiaohanshu1(chushizhongqunji[i]);
}
qsort(chushizhongqunji,glpgeshu,sizeof(chushi),&cmpshiyingjiang);//根據適應度將初始種群集按降序進行排列
chushi *youxiugetiku;//建立一個儲存優秀個體的庫
youxiugetiku=new chushi[glpgeshu];//建立一個儲存優秀個體的庫
int jishuqi=0;
i=0;
while(chushizhongqunji[i].shiying>zuiyougeti->shiying)//凡是比上一代的最優個體還要好的個體都放入優秀個體庫
{
for(int j=0;j<jiedeweishu;j++)
{
youxiugetiku[i].geti[j]=chushizhongqunji[i].geti[j];
//cout<<youxiugetiku[i].geti[j]<<endl;
}
//system("pause");
i++;
}
// cout<<i<<endl;//////////////
//system("pause");//////////////////////////////////////
jishuqi=i;//將得到的優秀個體的數量放入jishuqi保存
float *bianjiezancunqi;//下面就要以優秀個體庫中個體的范圍在成立一個局部搜索區域，所以先建立一個邊界暫存器
bianjiezancunqi=new float[jishuqi];
for(i=0;i<jiedeweishu;i++)
{
for(int j=0;j<jishuqi;j++)
{
bianjiezancunqi[j]=youxiugetiku[j].geti[i];//將優秀個體庫每一維的數據都放入bianjiezancunqi
}
qsort(bianjiezancunqi,jishuqi,sizeof(float),&cmp1);//對這些數據按降序排列，取兩個邊界又得到一個局部范圍
//將得到的范圍進行保存
zuobianjie[i]=bianjiezancunqi[jishuqi-1];
youbianjie[i]=bianjiezancunqi[0];
//cout<<zuobianjie[i]<<endl;//////////////////////////
// cout<<youbianjie[i]<<endl;///////////////////////////
//cout<<endl;///////////////////
//
if(zuobianjie[i]<zuobianjie2[i])//如果新得到的局部左邊界在上一代局部左邊界左邊，則左邊界取上一代的
{
zuobianjie[i]=zuobianjie2[i];
}
if(youbianjie[i]>youbianjie2[i])//如果新得到的局部右邊界在上一代局部右邊界右邊，則右邊界取上一代的
{
youbianjie[i]=youbianjie2[i];
}
}
if(chushizhongqunji[0].shiying>zuiyougeti->shiying)//本代種群的最優個體比歷史最有個個體好，則用本代的代替之，並將標志位賦值為1表示尋優成功
{
for(i=0;i<jiedeweishu;i++)
{
zuiyougeti->geti[i]=chushizhongqunji[0].geti[i];
}
zuiyougeti->shiying=chushizhongqunji[0].shiying;
biao=1;
}
delete [] bianjiezancunqi;
delete [] youxiugetiku;
for(i=0;i<glpgeshu;i++)
{
delete [] glp_shu_zu[i];
}
delete [] glp_shu_zu;
delete [] chushizhongqunji;
}
void jingyingbaoliu() //精英保留的實現
{
float glpshuliang,xiangliang[jiedeweishu];
if(biao==1)//如果尋優成功則利用局部搜索的數據
{
glpshuliang=glpgeshu1;
for(int i=0;i<jiedeweishu;i++)
{
xiangliang[i]=sheng_cheng_xiang_liang1[i];
}
}
else//否則利用全局搜索的數據
{
glpshuliang=glpgeshu2;
for(int i=0;i<jiedeweishu;i++)
{
xiangliang[i]=sheng_cheng_xiang_liang2[i];
}
}

chushi *chushizhongqunji;//建立一個用來儲存種群的容器
chushizhongqunji=new chushi[glpshuliang];
int i,j;

float **glp_shu_zu;//生成一個glp數組
glp_shu_zu=new (float *[glpshuliang]);
for(i=0;i<glpshuliang;i++)
{
glp_shu_zu[i]=new float[jiedeweishu];//生成的glp向量用glp_shu_zu儲存
}
glp glp_qiu_jie_first(glpshuliang,jiedeweishu);//定義生成多少組glp向量和向量的維數
glp_qiu_jie_first.glp_qiu_jie(glp_shu_zu,xiangliang);//將生成的glp向量用glp_shu_zu儲存，同時將生成向量帶入glp類
//cout<<"377"<<endl;
if(biao!=1)//如果尋優不成功則進入全局搜索
{
//cout<<"380"<<endl;////////////
float bianjiecha[jiedeweishu];
for(i=0;i<jiedeweishu;i++)
{
bianjiecha[i]=youbianjie3[i]-zuobianjie3[i];//計算上一代全局每一維范圍的寬度
}
static float rou=0.9;//定義收縮比
//float rou=pow(0.5,gen);
for(i=0;i<jiedeweishu;i++)//確定新的范圍
{
zuobianjie1[i]=zuiyougeti->geti[i]-rou*bianjiecha[i];//左邊界為以最優個體為中心-范圍寬度乘以收縮比
if(zuobianjie1[i]>zuobianjie2[i])//如果新的左邊界比目前局部左邊界大，那麼以目前的為全局尋優的左邊界
{
zuobianjie[i]=zuobianjie1[i];
zuobianjie3[i]=zuobianjie1[i];
}
else//否則以局部左邊界為全局左邊界
{
zuobianjie[i]=zuobianjie2[i];
zuobianjie3[i]=zuobianjie2[i];
}
youbianjie1[i]=zuiyougeti->geti[i]+rou*bianjiecha[i];//右邊界為以最優個體為中心+范圍寬度乘以收縮比
if(youbianjie1[i]<youbianjie2[i])
{
youbianjie[i]=youbianjie1[i];
youbianjie3[i]=youbianjie1[i];
}
else
{
youbianjie[i]=youbianjie2[i];
youbianjie3[i]=youbianjie2[i];
}
}
qsort(bianjiecha,jiedeweishu,sizeof(float),&cmp1);
if(cha==bianjiecha[0])//如果最大邊界差不變的話就將收縮因子變小
{
rou=pow(rou,2);
}

cha=bianjiecha[0];
}
//cout<<"421"<<endl;/////////////////////
for(i=0;i<glpshuliang;i++)//根據新產生的最優個體確定glp群
{
for(j=0;j<jiedeweishu;j++)
{
chushizhongqunji[i].geti[j]=sishewuru((zuobianjie[j]+(youbianjie[j]-(zuobianjie[j]))*glp_shu_zu[i][j]));
}
}
for(i=0;i<glpshuliang;i++)
{
mubiaohanshu1(chushizhongqunji[i]);
}
qsort(chushizhongqunji,glpshuliang,sizeof(chushi),&cmpshiyingjiang);
zuiyougetijicunqi->shiying=zuiyougeti->shiying;
if(chushizhongqunji[0].shiying>zuiyougeti->shiying)
{
for(i=0;i<jiedeweishu;i++)
{
zuiyougeti->geti[i]=chushizhongqunji[0].geti[i];
}
zuiyougeti->shiying=chushizhongqunji[0].shiying;
biao=1;
}
else
{
// cout<<"446"<<endl;/////////////
biao=0;
}

if(biao==1)//如果尋優成功了就需要確立一個新的局部最優解范圍
{
chushi *youxiugetiku;
youxiugetiku=new chushi[glpshuliang];
int jishuqi=0;
i=0;
while(chushizhongqunji[i].shiying>zuiyougetijicunqi->shiying)
{
for(int j=0;j<jiedeweishu;j++)
{
youxiugetiku[i].geti[j]=chushizhongqunji[i].geti[j];
}
i++;
}
jishuqi=i;
float *bianjiezancunqi;
bianjiezancunqi=new float[jishuqi];
for(i=0;i<jiedeweishu;i++)
{
for(int j=0;j<jishuqi;j++)
{
bianjiezancunqi[j]=youxiugetiku[j].geti[i];
}
qsort(bianjiezancunqi,jishuqi,sizeof(float),&cmp1);
zuobianjie[i]=bianjiezancunqi[jishuqi-1];
youbianjie[i]=bianjiezancunqi[0];
// cout<<zuobianjie[i]<<endl;//////////////
// cout<<youbianjie[i]<<endl;/////////////
// cout<<endl;///////////////
if(zuobianjie[i]<zuobianjie2[i])
{
zuobianjie[i]=zuobianjie2[i];
}
if(youbianjie[i]>youbianjie2[i])
{
youbianjie[i]=youbianjie2[i];
}
}
delete [] bianjiezancunqi;
delete [] youxiugetiku;
}

for(i=0;i<glpshuliang;i++)
{
delete [] glp_shu_zu[i];
}
delete [] glp_shu_zu;
delete [] chushizhongqunji;

}
void mubiaohanshu1(chushi &bianliang)//計算shiying
{
int i=0;
int sunshi,chanpin;
sunshi=qiegesushi*(bianliang.geti[0]+bianliang.geti[1]+bianliang.geti[2]+bianliang.geti[3]-1);
chanpin=chicun1*bianliang.geti[0]+chicun2*bianliang.geti[1]+chicun3*bianliang.geti[2]+chicun4*bianliang.geti[3];
bianliang.shiying=yuanmuchang-sunshi-chanpin;
if(bianliang.shiying!=0)//如果不能正好將木料分成所需尺寸則要多切一刀
{
sunshi=qiegesushi*(bianliang.geti[0]+bianliang.geti[1]+bianliang.geti[2]+bianliang.geti[3]);
}
if(bianliang.shiying<0)//罰函數
{
bianliang.shiying=bianliang.shiying+1e5;
}
bianliang.shiying=-bianliang.shiying;

}
int sishewuru(float x)
{
float y;
int z;
y=x-(int)x;
if(y<0.5)
{
z=(int)(x);
}
else
{
z=(int)x;
z=z+1;
}
return z;
}
glp.h源文件貼不下了，把你郵箱給我我發給你
郵箱：[email protected]

導航:首頁 > 源碼編譯 > 貪心演算法歷史背景

貪心演算法歷史背景

與貪心演算法歷史背景相關的資料