1.概述
1.1 算法的概念
算法設(shè)計(jì)應(yīng)滿足的目標(biāo)：正確性，可使用，可讀，健壯，高效率，低存儲
算法的5個(gè)重要特征：有限、確定、可行、輸入、輸出
通常用函數(shù)的返回值表示算法能否正確執(zhí)行，如果某個(gè)形參需要將執(zhí)行結(jié)果回傳給實(shí)參，需要將該形參設(shè)計(jì)為引用型參數(shù)
1.2 算法分析
算法分析是分析算法占用計(jì)算機(jī)資源的情況
算法分析的兩個(gè)主要方面是分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度
1.3 時(shí)間復(fù)雜度
一層循環(huán)：
- 列出循環(huán)趟數(shù)t與每趟循環(huán)i的變化值
- 找出t與i的關(guān)系(公式什么的)
- 找出循環(huán)結(jié)束條件
- 聯(lián)立兩式，解方程
兩層循環(huán)
- 列出外層循環(huán)i的變化值
- 列出內(nèi)層語句的執(zhí)行次數(shù)
- 內(nèi)層語句執(zhí)行次數(shù)*外層循環(huán)次數(shù)=結(jié)果
多層循環(huán)
方法1. 抽象為計(jì)算三維體積
方法2. 列式求和
1.4 空間復(fù)雜度
能不遞歸就不遞歸，遞歸占用的空間和時(shí)間復(fù)雜度太高了
循環(huán)占用的空間至始至終都是那個(gè)，但遞歸每次的函數(shù)空間都是新創(chuàng)的，就是不能重復(fù)利用。
2.選擇題
-
衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（C ）。
A 運(yùn)行速度快 B 占用空間少 C 時(shí)間復(fù)雜度低 D 代碼短 -
二分搜索算法是利用（ A ）實(shí)現(xiàn)的算法。
A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 -
以下不可以使用分治法求解的是（D ）。
A 棋盤覆蓋問題 B 選擇問題 C 歸并排序 D 0/1背包問題 -
實(shí)現(xiàn)循環(huán)賽日程表利用的算法是（ A ）。
A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 -
實(shí)現(xiàn)棋盤覆蓋算法利用的算法是（ A ）。
A、分治法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 -
實(shí)現(xiàn)合并排序利用的算法是（ A ）。
A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 -
使用分治法求解不需要滿足的條件是（A ）。
A 子問題必須是一樣的 B 子問題不能夠重復(fù)C 子問題的解可以合并 D 原問題和子問題使用相同的方法解 -
下列不是動態(tài)規(guī)劃算法基本步驟的是（ A ）。
A、找出最優(yōu)解的性質(zhì) B、構(gòu)造最優(yōu)解 C、算出最優(yōu)解 D、定義最優(yōu)解 -
下列是動態(tài)規(guī)劃算法基本要素的是（ D ）。
A、定義最優(yōu)解 B、構(gòu)造最優(yōu)解 C、算出最優(yōu)解 D、子問題重疊性質(zhì) -
最長公共子序列算法利用的算法是（ B ）。
A、分支界限法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 -
實(shí)現(xiàn)最大子段和利用的算法是（ B ）。
A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 -
矩陣連乘問題的算法可由（ B）設(shè)計(jì)實(shí)現(xiàn)。
A、分支界限算法 B、動態(tài)規(guī)劃算法 C、貪心算法 D、回溯算法 -
下列算法中通常以自底向上的方式求解最優(yōu)解的是（ B ）。
A、備忘錄法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 -
最大效益優(yōu)先是（ A ）的一搜索方式。
A、分支界限法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 -
下面不是分支界限法搜索方式的是（ D ）。
A、廣度優(yōu)先 B、最小耗費(fèi)優(yōu)先 C、最大效益優(yōu)先 D、深度優(yōu)先 -
廣度優(yōu)先是（ A ）的一搜索方式。
A、分支界限法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 -
一個(gè)問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問題的（ B ）。
A、重疊子問題 B、最優(yōu)子結(jié)構(gòu)性質(zhì) C、貪心選擇性質(zhì) D、定義最優(yōu)解 -
貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別是（ B ）。
A、最優(yōu)子結(jié)構(gòu) B、貪心選擇性質(zhì) C、構(gòu)造最優(yōu)解 D、定義最優(yōu)解 -
（ D ）是貪心算法與動態(tài)規(guī)劃算法的共同點(diǎn)。
A、重疊子問題 B、構(gòu)造最優(yōu)解 C、貪心選擇性質(zhì) D、最優(yōu)子結(jié)構(gòu)性質(zhì) -
背包問題的貪心算法所需的計(jì)算時(shí)間為（ B ）。
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） -
0-1背包問題的回溯算法所需的計(jì)算時(shí)間為（ A ）
A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） -
下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是（ D ）。
A、備忘錄法 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法 -
下面是貪心算法的基本要素的是（ C ）。
A、重疊子問題 B、構(gòu)造最優(yōu)解 C、貪心選擇性質(zhì) D、定義最優(yōu)解 -
下面問題（B ）不能使用貪心法解決。
A 單源最短路徑問題 B N皇后問題 C 最小花費(fèi)生成樹問題 D 背包問題 -
下列算法中不能解決0/1背包問題的是（A ）
A 貪心法 B 動態(tài)規(guī)劃 C 回溯法 D 分支限界法 -
回溯法解TSP問題時(shí)的解空間樹是（ A ）。
A、子集樹 B、排列樹 C、深度優(yōu)先生成樹 D、廣度優(yōu)先生成樹 -
回溯法的效率不依賴于下列哪些因素（ D ）
A.滿足顯約束的值的個(gè)數(shù) B. 計(jì)算約束函數(shù)的時(shí)間
C. 計(jì)算限界函數(shù)的時(shí)間 D. 確定解空間的時(shí)間 -
下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略（ B ）
A．遞歸函數(shù) B.剪枝函數(shù) C.隨機(jī)數(shù)函數(shù) D.搜索函數(shù) -
以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為 ( D ) 。
A、分支界限算法 B、概率算法 C、貪心算法 D、回溯算法 -
回溯法搜索狀態(tài)空間樹是按照（C ）的順序。
A 中序遍歷 B 廣度優(yōu)先遍歷 C 深度優(yōu)先遍歷 D 層次優(yōu)先遍歷
3.分治法
3.1 快速排序 (*)
#include <stdio.h>
#define SIZE 6
//快速排序
void quick_sort(int num[], int low, int high )
{
int i,j,temp; //temp是用來當(dāng)找到i和j并且i!=j時(shí)交換i和j的值
int tmp; //tmp用來保存基準(zhǔn)數(shù)
i = low; //num[low]也是基準(zhǔn)數(shù)
j = high;
tmp = num[low]; //任命為中間分界線，左邊比他小，右邊比他大,通常第一個(gè)元素是基準(zhǔn)數(shù)
if(i > j) //如果下標(biāo)i大于下標(biāo)j，函數(shù)結(jié)束運(yùn)行，這個(gè)一般出現(xiàn)在以分界線為軸之后，左邊或者把右邊只有一個(gè)數(shù)
{
return;
}
while(i != j)
{
while(num[j] >= tmp && j > i)
{
j--;
}
while(num[i] <= tmp && j > i)
{
i++;
}
if(j > i)
{
temp = num[j];
num[j] = num[i];
num[i] = temp;
}
}
// 直到i==j時(shí)
num[low] = num[i];
num[i] = tmp;
quick_sort(num,low,i-1);
quick_sort(num,i+1,high);
}
int main()
{
//創(chuàng)建一個(gè)數(shù)組
int num[SIZE];
int i;
//輸入數(shù)字
for(i =0; i < SIZE; i++)
{
scanf("%d",&num[i]);
}
quick_sort(num, 0, SIZE-1);
for(i = 0; i < SIZE; i++)
{
printf(" %d ", num[i]);
}
return 0;
}
移動方法：
- 在數(shù)組中選一個(gè)基準(zhǔn)數(shù)tmp（通常為數(shù)組第一個(gè)）；
- 數(shù)組中設(shè)置兩個(gè)哨兵i(初始指向數(shù)組第一個(gè))和j(初始指向數(shù)組最后一個(gè))；
- 先移動j，一次一次往前移,直到找到比tmp小的值(j>=tmp時(shí)都要往前移)；
- 再移動i，一次一次往后移,直到找到比tmp大的值(i<=tmp時(shí)都要往后移)；
- 當(dāng)找到符合條件的i和j的值時(shí)，i和j對應(yīng)的值互換，但是i和j指向的位置沒變；
- 當(dāng)i=j時(shí)，將i與tmp的值互換，i指向的位置沒變；
- 體現(xiàn)分治的地方來了：此時(shí)，以i指向的數(shù)作為軸，分開左右兩部分，每部分再按照上面的7個(gè)步驟再來一遍。
學(xué)習(xí)引用-快速排序
4.蠻力法
4.1 任務(wù)分配問題 (*)
問題描述：假設(shè)有n個(gè)任務(wù)需要分配給n個(gè)人執(zhí)行，每個(gè)任務(wù)只分配給一個(gè)人，每個(gè)人只分配一個(gè)任務(wù)，且第j個(gè)任務(wù)分配給第i個(gè)人的成本是C[i,> j]（1≤i , j≤n），任務(wù)分配問題要求找出總成本最小的分配方案。
用蠻力法解決任務(wù)分配生成成本矩陣，成本矩陣中相應(yīng)元素相加來求得每種分配方案的總成本
相應(yīng)解釋看代碼
#include <iostream>
#include <cstring>
using namespace std;
int visit[11],num[11];
int n,value = 9999999;
int martrix[4][4];
int lowNum[11];
/*檢驗(yàn)數(shù)據(jù)
4
9 2 7 8
6 4 3 7
5 8 1 8
7 6 9 4
*/
// 這個(gè)函數(shù)用于每一次在確定了num數(shù)組之后進(jìn)行對應(yīng)的總成本計(jì)算
void findLowCost() {
int sum = 0;
for(int i = 1; i <= n; i++) {
sum += martrix[i - 1][num[i] - 1];
}
if(sum < value) {
for(int i=1;i<=n;i++){
lowNum[i]=num[i];
}
value = sum;
}
}
/*
visit代表當(dāng)前i任務(wù)是否被選擇
i的取值：1，2，3，4；代表任務(wù)種類
num數(shù)組代表人員，
num[length]：里面的length代表第幾個(gè)人，用1，2，3，4區(qū)分，共四個(gè)人
*/
void dfs(int length) {
if(length > n) {
findLowCost();
} else {
for(int i = 1; i <= n; i++) {
if(visit[i] == 0) {
visit[i] = 1; //visit[i]=1代表當(dāng)前i任務(wù)是否被選擇
num[length] = i; //num[length] = i代表第length個(gè)人選擇了第i個(gè)任務(wù)
dfs(length + 1);
visit[i] = 0;
//visit[i]重新置為0，代表在一次分配方案之后
//(就是每個(gè)人都分配到一種任務(wù)，每個(gè)任務(wù)只分配給一個(gè)人)
//當(dāng)length > n進(jìn)行了findLowCost函數(shù)之后，回退至length=n-1，以為length==n的那個(gè)循環(huán)已經(jīng)走完了
//在 length=n-1時(shí)，visit置0，，但還有一個(gè)i需要走循環(huán)，這又是一個(gè)方案
// 依次循環(huán)回退走完所有方案。
}
}
}
}
int main() {
cin >> n;
memset(visit,0,sizeof(visit)); //visit全置為0，代表任務(wù)全沒被選擇
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
cin >> martrix[i][j];
}
}
dfs(1);
cout<<"最小成本分配方案:"<<endl;
for(int i=1;i<=n;i++){
cout<<"第"<<i<<"個(gè)人選擇的任務(wù)是:"<<lowNum[i]<<endl;
}
cout << "最小成本:" <<value;
return 0;
}
學(xué)習(xí)引用-任務(wù)分配蠻力法
5.回溯法
5.0 回溯法的概念
在搜索嘗試過程中尋找問題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件時(shí)(設(shè)置的判斷條件稱為“剪枝函數(shù)”)，就往回移動（回溯），嘗試別的路徑
回溯法思路的簡單描述是：把問題的解空間轉(zhuǎn)化成了圖或者樹的結(jié)構(gòu)表示，然后使用深度優(yōu)先搜索策略進(jìn)行遍歷，遍歷的過程中記錄和尋找所有可行解或者最優(yōu)解。
與分支限界法的聯(lián)系：使用剪枝函數(shù)的深度優(yōu)先生成狀態(tài)空間樹中的節(jié)點(diǎn)的求解方法稱為回溯法；廣度優(yōu)先生成結(jié)點(diǎn)，并使用剪枝函數(shù)的方法稱為分枝限界法
5.1 裝載問題 (*)
- 問題描述：現(xiàn)有 n 件貨物 (Cargo) 每件貨物的重量(weight)是 Wi ( 0<i≤n , i∈ N ), 需要把這 n 件貨物全部裝上兩艘船 shipOne 和 shipTwo , 兩艘船的最大容量為Capacity1 和 Capacity2 問是否有一種合理的方案使得全部貨物都能裝上船?
- 代碼
package com.ljh;
class Cargo {
int weight = 0; //貨物重量
boolean isLoad = false; //貨物是否被裝載上船狀態(tài)
}
class Ship {
int capacity = 0; //船的容量
int minMargin; //目前得到的最小余量(不斷縮小)-就是剩余的船的容量的最小值
int nowMargin; //現(xiàn)在的船上余量
int nowWeight; //現(xiàn)在船上貨物的重量
int numOfCargo; //船上貨物數(shù)量
Cargo[] cargo;
Cargo[] realCargo;
public Ship(int capacity) {
this.capacity = capacity;
this.minMargin = capacity;
this.nowMargin = capacity;
}
//這里使用重載是為了區(qū)分兩艘船的作用.
public Ship(int capacity, Cargo cargo[], Cargo realCargo[]) {
this.capacity = capacity;
this.cargo = cargo;
this.realCargo = realCargo;
this.numOfCargo = cargo.length; //初始化時(shí)船上的貨物個(gè)數(shù)=總貨物個(gè)數(shù)
this.minMargin = capacity;
this.nowMargin = capacity;
this.nowWeight = 0;
}
}
public class BackTrackAlgorithm {
//聲明全部所需的變量,我們需要裝載的貨物重量,它的總重量,兩艘船,貨物對象.
static int aboutCargo[] = {90, 80, 40, 30, 20, 12, 10};
static int totalWeight;
static Ship shipOne;
static Ship shipTwo;
static Cargo[] cargo = new Cargo[aboutCargo.length]; //聲明cargo數(shù)組
static Cargo[] realCargo = new Cargo[aboutCargo.length]; //不用先思考readlCargo的作用在后面會給出解釋
static int i = 0; //見后
//在main中直接調(diào)用兩個(gè)方法得出解
public static void main(String[] args) {
BackTrackAlgorithm bta = new BackTrackAlgorithm();
bta.init();
bta.getResult();
}
//初始化船,并使用回溯法,使得我們的問題得出最優(yōu)方案
public void init() {
for (int j = 0; j < aboutCargo.length; j++) {
cargo[j] = new Cargo();
realCargo[j] = new Cargo();
realCargo[j].weight = aboutCargo[j];
cargo[j].weight = aboutCargo[j];
totalWeight += aboutCargo[j]; //計(jì)算總的貨物重量
}
shipOne = new Ship(152, cargo, realCargo); //這里代表我先以shipOne做考慮
shipTwo = new Ship(130);
//開始建立樹結(jié)構(gòu)
while (true) {
//進(jìn)行每一輪的選擇
while (i < shipOne.numOfCargo) {
if ((shipOne.nowWeight + shipOne.cargo[i].weight) <= shipOne.capacity) {//判斷條件
shipOne.nowWeight += shipOne.cargo[i].weight;//變化當(dāng)前重量
shipOne.nowMargin -= shipOne.cargo[i].weight;//變化當(dāng)前余量
shipOne.cargo[i].isLoad = true;//確認(rèn)i貨物裝載上船
i += 1;
} else {
shipOne.cargo[i].isLoad = false;//不裝載,繼續(xù)往下走
i += 1;
}
}
//經(jīng)過上面已經(jīng)得到shipOne的一個(gè)方案
//進(jìn)行一輪的選擇之后是否得到更優(yōu)的方案
//這里改變r(jià)ealCargo[j].isLoad才是代表真正最優(yōu)方案
if (shipOne.nowMargin < shipOne.minMargin) {
shipOne.minMargin = shipOne.nowMargin;
//如果得到更優(yōu)的方案,我們需要存入這一輪的貨物選擇情況,為什么要使用另一個(gè)realCargo數(shù)組,請閱讀代碼后思考片刻
for (int j = 0; j < shipOne.numOfCargo; j++) {
if (shipOne.cargo[j].isLoad == true) {
shipOne.realCargo[j].isLoad = true;
}
if (shipOne.cargo[j].isLoad == false) {
shipOne.realCargo[j].isLoad = false;
}
}
}
//進(jìn)入回溯法,回溯的就是我們之前設(shè)置的靜態(tài)屬性 i 即我們選擇的貨物貨號
i = backtrace(i - 1);//為什么是 i-1:i-1才是判斷的最后一個(gè)貨物貨號
//退出的條件,我們是否已經(jīng)結(jié)束最后一輪.
if (i == 0) {
return;
}
}
}
//回溯法
public int backtrace(int j) {
//請讀者思考作用.
while (j > 0 && shipOne.cargo[j].isLoad == false) {
j -= 1;
}
//請讀者思考作用.
if (shipOne.cargo[j].isLoad == true) {
shipOne.cargo[j].isLoad = false;
shipOne.nowMargin += shipOne.cargo[j].weight;
shipOne.nowWeight -= shipOne.cargo[j].weight;
j += 1;
}
return j;
/**
* tips:這里每輪的回溯會改變shipOne.cargo[i].isLoad,最后得到的自然是最后一輪選擇方案,
* 但最后一輪得到的不一定是最優(yōu)解,所以我們肯定需要另外一個(gè)Cargo數(shù)組來記錄更優(yōu)方案 即前面
* 聲明的readCargo[]
*/
}
//返回最優(yōu)結(jié)果集
public void getResult() {
//判斷是否有解
if ((totalWeight - (shipOne.capacity - shipOne.minMargin)) <= shipTwo.capacity) {
System.out.println("\n本問題有合理的方案.\n");
for (int j = 0; j < aboutCargo.length; j++) {
if (shipOne.realCargo[j].isLoad == true) {
System.out.println("貨物 " + j + " 已經(jīng)裝載上船1,重量是:" + shipOne.realCargo[j].weight);
}
if(shipOne.realCargo[j].isLoad==false) {
System.out.println("貨物 " + j + " 將會裝載上船2,重量是:" + shipOne.realCargo[j].weight);
}
}
} else {
System.out.println("經(jīng)過努力的嘗試,得出本問題沒有合理的方案使得全部貨物裝上兩艘船,抱歉");
}
}
}
解題思路：
回溯法是將問題的 解 抽象成 圖或者樹的結(jié)構(gòu)來表示.
在裝載問題中,對于每個(gè)貨物我們的選擇只有 選擇 / 不選 所以我們選擇抽象成樹的結(jié)構(gòu),對于選擇此貨物自然對應(yīng) 1/true
對于不選擇此貨物對應(yīng) 0/true , 依次對每個(gè)貨物進(jìn)行選擇,我們自然會得到 2^n個(gè)解 但是我們當(dāng)然沒有必要把所有結(jié)果都列舉出來,
例如以下例子 :W 為貨物的重量的集合c1,c2為兩艘船的總?cè)萘?設(shè)置判斷條件為: 已經(jīng)裝上的 貨物重量 加上 下一個(gè)貨物
后的重量不大于shipOne的容量,那么就可以裝上此貨物 .若大于則選擇不裝此貨物 這樣自然就可以得到一棵得到 優(yōu)化結(jié)果集的子樹 .但是經(jīng)過第一輪的選擇之后,雖然得到了第一個(gè)方案,但是我們不能保證這是最優(yōu)的解 , 不能確定是最優(yōu)的方案就不能保證我們的問題是否有解 ,
所以只有經(jīng)過多輪不同的選擇 才能得到最優(yōu)的方案,才能得出問題是否有解.那么 , 如何進(jìn)行多輪的選擇? 怎么才能知道 哪一輪選擇的方案是最好的? 前面提到余容量就是我們判斷是否是更優(yōu)方案的指標(biāo)
剩余容量越小,則說明這樣的方案更優(yōu).知道如何判斷是否是更優(yōu)的方案之后,我們就要思考如何遍歷這棵樹能更快的得出結(jié)果集,如果從頭開始遍歷,自然是效率最低選擇,因?yàn)槲覀儠貜?fù)走我們已經(jīng)走過的路.
所以我們不妨進(jìn)行回溯, 如下圖所示: 我們第一輪得出的結(jié)果是90+0+40+0+20+0+0 ,于是從最后一個(gè)貨物 ( 重量為10的貨物開始回溯 ) 對于已經(jīng)選擇為 0/false
的物品我們自然不需要再去遍歷它的左子樹了,因?yàn)槲覀儽旧砭脱b不下它 . 所以我們?nèi)ケ闅v右子樹 . 于是我們往上回溯 ,
找到以第一個(gè)我們已經(jīng)選擇的貨物 ,我們這一輪 ( 第二輪從選擇重量為20的貨物開始 ) 就不裝載 重量為 20的貨物,
我們想要去選擇剩下的其余貨物(12 和 10).進(jìn)行第二輪的選擇后 會得到一個(gè)解決方案,我們自然就可以比較 余量(Margin)
是否較前一種方案更優(yōu) 接著我們繼續(xù)回溯…一直到我們進(jìn)行最后一輪回溯 , 最后一輪便是從我們之前選擇的第一個(gè)貨物開始,一來就不裝載 (
重量為90的貨物 ) 此貨物. 最后進(jìn)行一輪選擇. 最后就可以得到我們的最優(yōu)方案 , 以此便可以確定我們的問題 , 是否有解.
左子樹有值代表選中，左子樹為0代表未選中
學(xué)習(xí)引用-裝配問題回溯法
6.分支限界法
6.1 流水作業(yè)調(diào)度問題 (*)
問題描述：有n個(gè)作業(yè)（編號為1～n）要在由兩臺機(jī)器M1和M2組成的流水線上完成加工。每個(gè)作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時(shí)間分別為ai和bi（1≤i≤n）。
流水作業(yè)調(diào)度問題要求確定這n個(gè)作業(yè)的最優(yōu)加工順序，使得從第一個(gè)作業(yè)在機(jī)器M1上開始加工，到最后一個(gè)作業(yè)在機(jī)器M2上加工完成所需的時(shí)間最少?？梢约俣ㄈ魏巫鳂I(yè)一旦開始加工，就不允許被中斷，直到該作業(yè)被完成，即非優(yōu)先調(diào)度
關(guān)鍵公式：對于按1～n順序執(zhí)行的某種調(diào)度方案，f1表示在M1上執(zhí)行完當(dāng)前第i步的作業(yè)對應(yīng)的總時(shí)間，f2數(shù)組表示在M2上執(zhí)行完當(dāng)前第i步的作業(yè)的總時(shí)間。
若第i步執(zhí)行作業(yè)j，計(jì)算公式如下：
f1=f1+a[j];
f2[i]=max(f1，f2[i-1])+b[j]
代碼：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define INF 999999
#define MAX 5
using namespace std;
//問題表示
int n=4; //作業(yè)數(shù)
int a[MAX]={0,5,10,9,7};//M1上的執(zhí)行時(shí)間,不用下標(biāo)0的元素
int b[MAX]={0,7,5,9,8};//M2上的執(zhí)行時(shí)間,不用下標(biāo)0的元素
//求解結(jié)果表示
int bestf=INF;//存放最優(yōu)調(diào)度時(shí)間
int bestx[MAX];//存放當(dāng)前作業(yè)最佳調(diào)度
int total=1;//結(jié)點(diǎn)個(gè)數(shù)累計(jì)
struct NodeType//隊(duì)列結(jié)點(diǎn)類型
{
int no;//結(jié)點(diǎn)編號
int x[MAX];//x[i]表示第i步分配作業(yè)編號
int y[MAX];//y[i]=1表示編號為i的作業(yè)已經(jīng)分配
int i;//步驟編號
int f1;//f1表示在M1上執(zhí)行完當(dāng)前第i步的作業(yè)對應(yīng)的總時(shí)間
int f2;//f2表示在M2上執(zhí)行完當(dāng)前第i步的作業(yè)的總時(shí)間
int lb;//下界
bool operator<(const NodeType &s) const//重載<關(guān)系函數(shù)
{
return lb>s.lb;//lb越小越優(yōu)先出隊(duì)
}
};
void bound(NodeType &e)//求結(jié)點(diǎn)e的限界值
{
int sum=0;
for(int i=1;i<=n;i++)//掃描所有作業(yè)
{
if(e.y[i]==0) //編號為i的作業(yè)未分配
{
sum+=b[i];//僅累計(jì)e.x中還沒有分配的作業(yè)的在M2上的執(zhí)行時(shí)間
}
}
e.lb=e.f1+sum;
}
void bfs()//求解流水作業(yè)調(diào)度問題
{
NodeType e,e1; priority_queue<NodeType> qu;//定義優(yōu)先隊(duì)列
memset(e.x,0,sizeof(e.x));//初始化根結(jié)點(diǎn)的x
memset(e.y,0,sizeof(e.y));//初始化根結(jié)點(diǎn)的y
e.i=0;//根結(jié)點(diǎn)
e.f1=0;
e.f2=0;
bound(e);
e.no=total++;
qu.push(e);//根結(jié)點(diǎn)進(jìn)隊(duì)列
while(!qu.empty())
{
e=qu.top();
qu.pop(); //出隊(duì)結(jié)點(diǎn)e
if(e.i==n) //達(dá)到葉子結(jié)點(diǎn)
{
if(e.f2<bestf) //比較求最優(yōu)解
{
bestf=e.f2;
for(int j1=1;j1<=n;j1++)
{
bestx[j1]=e.x[j1];//在第j1步分配對應(yīng)的作業(yè)
}
}
}
e1.i=e.i+1;//擴(kuò)展分配下一個(gè)步驟的作業(yè)，對應(yīng)結(jié)點(diǎn)e1
for(int j=1;j<=n;j++)//考慮所有的n個(gè)作業(yè)
{
if(e.y[j]==1)
{
continue;//作業(yè)j是否已分配,若已分配，跳過
}
//若作業(yè)j還未被分配：
for(int i1=1;i1<=n;i1++)//復(fù)制e.x得到e1.x
{
e1.x[i1]=e.x[i1];
}
for(int i2=1;i2<=n;i2++)//復(fù)制e.y得到e1.y
{
e1.y[i2]=e.y[i2];
}
e1.x[e1.i]=j;//為第i步分配作業(yè)j
e1.y[j]=1;//表示作業(yè)j已經(jīng)分配
e1.f1=e.f1+a[j];//求f1=f1+a[j]
e1.f2=max(e.f2,e1.f1)+b[j];//求f[i+1]=max(f2[i],f1)+b[j]
bound(e1);
if(e1.f2<=bestf)//剪枝,剪去不可能得到更優(yōu)解的結(jié)點(diǎn)
{
e1.no=total++;//結(jié)點(diǎn)編號增加1
qu.push(e1);
}
}
}
}
int main()
{
bfs();
cout<<"Optimal plan is :"<<endl;
for(int k=1;k<=n;k++)
{
cout<<"The "<<k<<" step is to execute the job is :"<<bestx[k]<<endl;
}
cout<<"The total time is :"<<bestf<<endl;
return 0;
}
學(xué)習(xí)引用-流水作業(yè)分支界限法
7.貪心法
7.0 貪心算法的理解
貪心算法并不從整體最優(yōu)上加以考慮，所作出的僅是某種意義上的局部最優(yōu)選擇,要確定一個(gè)問題是否適合使用貪心算法解題，必須證明每一步所做的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解
7.1 活動安排問題 (*)
由于輸入的活動是以其完成時(shí)間升序排列的，所以每次總是選擇具有最早完成時(shí)間的活動加入集合 selected 中
代碼：
#include <stdio.h>
#define N 100
/*檢驗(yàn)數(shù)據(jù)
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
11 14
*/
/*
n:活動個(gè)數(shù)
s:開始時(shí)間數(shù)組
t:結(jié)束時(shí)間數(shù)組
selected:活動選擇數(shù)組
*/
void greedyselector(int n, int s[], int f[], int selected[])
{
int i;
int j = 1; //j記錄最近一次加入到a中的活動
selected[1] = 1; //首先選擇活動1
for (i = 2; i <= n; i ++)
if (s[i] >= f[j]) { //如果活動i與活動j兼容，則選擇活動i
// 兼容性的判斷：下一個(gè)活動的開始時(shí)間>=上一個(gè)活動的結(jié)束時(shí)間
selected[i] = 1;
j = i;
}
else
selected[i] = 0;
}
int main()
{
int s[N], f[N]; //s[i],f[i]存儲活動 i的開始和結(jié)束時(shí)間
int selected[N]; //若活動 i被選擇，則selected[i]置1，否則置0
int n,i;
printf("請輸入活動個(gè)數(shù)：");
scanf("%d", &n);
printf("請輸入各個(gè)活動的開始和結(jié)束時(shí)間（要求按結(jié)束時(shí)間升序輸入）：\n");
for (i = 1; i <= n; i ++) //從i=1開始掃描
scanf("%d%d", &s[i], &f[i]);
greedyselector(n, s, f, selected);
printf("如下活動被選擇：\n");
for (i = 1; i <= n; i ++)
if (selected[i] == 1)
printf("%d ", i);
printf("\n");
return 0;
}
學(xué)習(xí)引用-活動安排貪心算法
8.動態(tài)規(guī)劃法
8.0 什么是動態(tài)規(guī)劃：
動態(tài)規(guī)劃是一種解決多階段決策問題的優(yōu)化方法，把多階段過程轉(zhuǎn)化為一系列單階段問題
8.1 0/1背包問題 (*)
這個(gè)問題是有個(gè)前提條件：就是每個(gè)物品你最多只能拿一次(也就是說一個(gè)物品你要嗎不拿就是拿0次，拿就只能拿1次，所以叫0/1問題)
遞推樹
狀態(tài)轉(zhuǎn)移方程
代碼：
package com.ljh;
public class package01_DP {
/**
* 0-1背包
*
* @param val 價(jià)值
* @param weight 重量
* @param W 背包容量
* @return 最優(yōu)解
*/
public static int MaxValueWithDP(int[] val, int[] weight, int W) {
int N = weight.length; //物品數(shù)
// 創(chuàng)建背包矩陣，矩陣的行數(shù)是物品數(shù)量+1；矩陣的列數(shù)是物品重量+1
int[][] V = new int[N + 1][W + 1];
//初始化矩陣第一行，背包容量為0
for (int col = 0; col <= W; col++) {
V[0][col] = 0;
}
//初始化矩陣第一列，背包容量為0
for (int row = 0; row <= N; row++) {
V[row][0] = 0;
}
for (int i = 1; i <= N; i++) { //一行一行填充值，i = 1從第二行開始填
for (int j = 1; j <= W; j++) { //一列一列填充值，j = 1從第二列開始填
if (weight[i - 1] <= j) { //如果當(dāng)前物品重量小于等于背包中的當(dāng)前重量 i為1是，weight[0]是第一個(gè)物品的重量
/*比較不加入該物品時(shí)該重量的最大價(jià)值（前一行）V[i - 1][j]
*與
*當(dāng)前物品的價(jià)值val[i - 1]+沒放該物品之前,背包已有重量的最大價(jià)值V[i - 1][j - weight[i - 1]]
*/
V[i][j] = Math.max(val[i - 1] + V[i - 1][j - weight[i - 1]], V[i - 1][j]);
} else { //如果當(dāng)前物品重量大于背包中的當(dāng)前重量
V[i][j] = V[i - 1][j]; //直接使用前一行的最優(yōu)解
}
}
}
// 打印矩陣
for (int[] rows : V) {
for (int col : rows) {
System.out.format("%5d", col);
}
System.out.println();
}
return V[N][W];
}
public static void main(String[] args) {
int val[] = {3, 4, 5, 8}; //物品價(jià)值數(shù)組
int weight[] = {2, 3, 4, 5}; //物品重量數(shù)組
int W = 8; //背包重量
int MaxValue = MaxValueWithDP(val, weight, W);
System.out.println("當(dāng)前背包的最大價(jià)值是:" + MaxValue);
}
}
根據(jù)代碼做出動態(tài)轉(zhuǎn)移表
文章來源：http://www.zghlxwxcb.cn/news/detail-772376.html
學(xué)習(xí)引用-0/1背包問題動態(tài)規(guī)劃法文章來源地址http://www.zghlxwxcb.cn/news/detail-772376.html
到了這里，關(guān)于算法設(shè)計(jì)與分析-期末復(fù)習(xí)經(jīng)典例題的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
