算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告三

貴州師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院實(shí)驗(yàn)報(bào)告課程名稱(chēng)：算法設(shè)計(jì)與分析班級(jí)：13計(jì)本實(shí)驗(yàn)日期：2015.11.30學(xué)號(hào)：115703020052姓名：吳道鎂指導(dǎo)教師：熊祥光成績(jī)：一、實(shí)驗(yàn)名稱(chēng)貪心算法——最優(yōu)裝載問(wèn)題二、實(shí)驗(yàn)?zāi)康募耙?、掌握貪心算法的基本思想；2、利用貪心算法思想，編程實(shí)現(xiàn)最優(yōu)裝載問(wèn)題；3、能對(duì)所設(shè)計(jì)算法的計(jì)算復(fù)雜性進(jìn)行分析；4、對(duì)于給定的實(shí)例，能給出相應(yīng)算法的計(jì)算過(guò)程。三、實(shí)驗(yàn)工具XP系統(tǒng)或Win7系統(tǒng)，編程語(yǔ)言不限四、實(shí)驗(yàn)內(nèi)容1、編程語(yǔ)言不限，實(shí)現(xiàn)教材P95頁(yè)的貨船最優(yōu)裝載算法并對(duì)該算法的復(fù)雜性進(jìn)行分析。算法的實(shí)現(xiàn)：#include"stdafx.h"#include<iostream>usingnamespacestd;constintN=4;template<classType>voidSwap(Type&x,Type&y);template<classType>voidLoading(intx[],Typew[],Typec,intn);template<classType>voidSelectSort(Typew[],int*t,intn);intmain(){floatc=70;floatw[]={0,20,10,26,15};//下標(biāo)從1開(kāi)始intx[N+1];cout<<"輪船載重為："<<c<<endl;cout<<"待裝物品的重量分別為："<<endl;for(inti=1;i<=N;i++){cout<<w[i]<<"";}cout<<endl;Loading(x,w,c,N);cout<<"貪心選擇結(jié)果為:"<<endl;for(inti=1;i<=N;i++){cout<<x[i]<<"";}cout<<endl;return0;}template<classType>voidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];//存儲(chǔ)排完序后w[]的原始索引SelectSort(w,t,n);for(inti=1;i<=n;i++){x[i]=0;//初始化數(shù)組x[]}for(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}}template<classType>voidSelectSort(Typew[],int*t,intn){TypetempArray[N+1],temp;memcpy(tempArray,w,(n+1)*sizeof(Type));//將w拷貝到臨時(shí)數(shù)組tempArray中intmin;for(inti=1;i<=n;i++){t[i]=i;}for(inti=1;i<n;i++){min=i;for(intj=i+1;j<=n;j++){if(tempArray[min]>tempArray[j]){min=j;}}Swap(tempArray[i],tempArray[min]);Swap(t[i],t[min]);}}template<classType>voidSwap(Type&x,Type&y){Typetemp=x;x=y;y=temp;}實(shí)驗(yàn)結(jié)果：2、假設(shè)某公司現(xiàn)有8個(gè)集裝箱急需搬上一艘大貨船，它們的重量分別是[W0,W2,…,W7]=[100,200,50,90,150,50,20,80]，船只載重C=400。求該條件下的最優(yōu)裝載問(wèn)題。（要求給出具體的過(guò)程）1.首先對(duì)集裝箱按重量大小進(jìn)行排序：20,50,50,80,90,100,150,200編號(hào)為m1至m8。2.按順序?qū)b箱裝入貨船，滿(mǎn)足集裝箱重量之和小于等于船只載重C,當(dāng)滿(mǎn)足這個(gè)條件時(shí)的裝入的集裝箱數(shù)量為最