求解一道貪心算法

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

專注于為中小企業(yè)提供做網(wǎng)站、網(wǎng)站制作服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)雁山免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了上千多家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。

下面就根據(jù)你給出的例子講解一下：

對于6000的料來說

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

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

設(shè)第一加工出的產(chǎn)品量分別為1 1 3 1

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

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

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

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

下面是我跟據(jù)對你給出的例子的理解算出的結(jié)果。

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根

請按任意鍵繼續(xù). . .

程序代碼如下：（變量都是用漢語拼音標(biāo)的）

#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 shiyingdu;

};

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

chushi *zuiyougetijicunqi;

int sishewuru(float);

float chazhi;//左右邊界的差

int biaozhi;//判斷尋優(yōu)是否成功1表示成功0表示不成功

int maxgen;//最大計算代數(shù)

int gen;//目前代數(shù)

void initialize();//算法初始化

void jingyingbaoliu();//精英保存的實現(xiàn)

void mubiaohanshu1(chushi bianliang);//適應(yīng)度的計算使用殘差法

int cmpshiyingdujiang(const void *p1,const void *p2)

{

float i=((chushi *)p1)-shiyingdu;

float j=((chushi *)p2)-shiyingdu;

return ij ? 1:(i==j ? 0:-1);//現(xiàn)在是按降序牌排列，將1和-1互換后就是按升序排列

}

int cmp1(const void *p1,const void *p2)

{

float i= *(float*)p1;

float j= *(float*)p2;

return ij ? 1:(i==j ? 0:-1);//現(xiàn)在是按降序牌排列，將1和-1互換后就是按升序排列

}

void main()

{

float bianjiebianhuashuzu[jiedeweishu];

float yiwanchengshuliang[jiedeweishu];

zuiyougeti=new chushi;//最優(yōu)個體的生成

zuiyougetijicunqi=new chushi;

int i;

for(i=0;ijiedeweishu;i++)

{

zuiyougeti-geti[i]=0;

yiwanchengshuliang[i]=0;

}

int muliaoshuliang=0;

while(1)

{

if(yiwanchengshuliang[0]==chicun1shuliangyiwanchengshuliang[1]==chicun2shuliangyiwanchengshuliang[2]==chicun3shuliangyiwanchengshuliang[3]==chicun4shuliang)

break;//都加工完了就退出程序

biaozhi=1;

for(i=0;ijiedeweishu;i++)

{

bianjiebianhuashuzu[i]=chicunxuqiuliang[i]-yiwanchengshuliang[i];

}

for(i=0;ijiedeweishu;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;ijiedeweishu;i++)

{

zuobianjie[i]=zuobianjie0[i];

youbianjie[i]=youbianjie0[i];

}

for(i=0;ijiedeweishu;i++)//在這套程序中邊界分為兩個部分,其中一組是根據(jù)最優(yōu)解的收斂范圍進(jìn)行局部尋優(yōu),如果在局部找不到最優(yōu)解則以現(xiàn)有最優(yōu)解為中心進(jìn)行全局搜索

{

zuobianjie2[i]=zuobianjie[i];

youbianjie2[i]=youbianjie[i];

zuobianjie3[i]=zuobianjie[i];

youbianjie3[i]=youbianjie[i];

}

zuiyougeti-shiyingdu=-3000;

//cout zuiyougeti-shiyingduendl;

initialize();

//for(i=0;ijiedeweishu;i++)/////

//{////

// coutzuiyougeti-geti[i]",";////

//}/////////

//coutendl;/////

// cout"初始最優(yōu)解："" "-zuiyougeti-shiyingduendl;/////////////

for(gen=1;genmaxgen;gen++)

{

jingyingbaoliu();

if(chazhi1e-1)

break;

}

//cout"最終在收斂的范圍內(nèi)左右邊界的最大差值: "chazhiendl;

//for(i=0;ijiedeweishu;i++)

//{

// coutsetiosflags(ios::fixed)setprecision(6)zuiyougeti-geti[i]",";

// }

//coutendl;

//cout"共用代數(shù)"genendl;

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-shiyingdu)endl;////////////////

coutendl;

for(i=0;ijiedeweishu;i++)

{

yiwanchengshuliang[i]=yiwanchengshuliang[i]+zuiyougeti-geti[i];

}

muliaoshuliang++;

}

cout"用去木料："muliaoshuliang"根"endl;

delete [] zuiyougetijicunqi;

delete [] zuiyougeti;

system("pause");

}

void initialize()

{

maxgen=20;//最大代數(shù)

gen=0;//起始代

chazhi=100;

chushi *chushizhongqunji;

chushizhongqunji=new chushi[glpgeshu];

int i,j;

for(i=0;ijiedeweishu;i++)

{

zuobianjie1[i]=zuobianjie[i];

youbianjie1[i]=youbianjie[i];

}

float **glp_shu_zu;//第一次求解，為了使解更精確這一次求解需要的點最多

glp_shu_zu=new (float *[glpgeshu]);

for(i=0;iglpgeshu;i++)

{

glp_shu_zu[i]=new float[jiedeweishu];//生成的glp向量用glp_shu_zu儲存

}

glp glp_qiu_jie_first(glpgeshu,jiedeweishu);//定義生成多少組glp向量和向量的維數(shù)

glp_qiu_jie_first.glp_qiu_jie(glp_shu_zu,sheng_cheng_xiang_liang);//將生成的glp向量用glp_shu_zu儲存，同時將生成向量帶入glp類

for(i=0;iglpgeshu;i++)//產(chǎn)生初始種群

{

for(j=0;jjiedeweishu;j++)

{

chushizhongqunji[i].geti[j]=sishewuru((zuobianjie[j]+(youbianjie[j]-(zuobianjie[j]))*glp_shu_zu[i][j]));

if(j==3glp_shu_zu[i][j]0)

{

cout"274"endl;/////////////

coutzuobianjie[j]" "glp_shu_zu[i][j]" "youbianjie[j]endl;////////////////////

system("pause");///////////////////

}

}

}

for(i=0;iglpgeshu;i++)//計算初始種群的適應(yīng)度

{

mubiaohanshu1(chushizhongqunji[i]);

}

qsort(chushizhongqunji,glpgeshu,sizeof(chushi),cmpshiyingdujiang);//根據(jù)適應(yīng)度將初始種群集按降序進(jìn)行排列

chushi *youxiugetiku;//建立一個儲存優(yōu)秀個體的庫

youxiugetiku=new chushi[glpgeshu];//建立一個儲存優(yōu)秀個體的庫

int jishuqi=0;

i=0;

while(chushizhongqunji[i].shiyingduzuiyougeti-shiyingdu)//凡是比上一代的最優(yōu)個體還要好的個體都放入優(yōu)秀個體庫

{

for(int j=0;jjiedeweishu;j++)

{

youxiugetiku[i].geti[j]=chushizhongqunji[i].geti[j];

//coutyouxiugetiku[i].geti[j]endl;

}

//system("pause");

i++;

}

// coutiendl;//////////////

//system("pause");//////////////////////////////////////

jishuqi=i;//將得到的優(yōu)秀個體的數(shù)量放入jishuqi保存

float *bianjiezancunqi;//下面就要以優(yōu)秀個體庫中個體的范圍在成立一個局部搜索區(qū)域，所以先建立一個邊界暫存器

bianjiezancunqi=new float[jishuqi];

for(i=0;ijiedeweishu;i++)

{

for(int j=0;jjishuqi;j++)

{

bianjiezancunqi[j]=youxiugetiku[j].geti[i];//將優(yōu)秀個體庫每一維的數(shù)據(jù)都放入bianjiezancunqi

}

qsort(bianjiezancunqi,jishuqi,sizeof(float),cmp1);//對這些數(shù)據(jù)按降序排列，取兩個邊界又得到一個局部范圍

//將得到的范圍進(jìn)行保存

zuobianjie[i]=bianjiezancunqi[jishuqi-1];

youbianjie[i]=bianjiezancunqi[0];

//coutzuobianjie[i]endl;//////////////////////////

// coutyoubianjie[i]endl;///////////////////////////

//coutendl;///////////////////

//

if(zuobianjie[i]zuobianjie2[i])//如果新得到的局部左邊界在上一代局部左邊界左邊，則左邊界取上一代的

{

zuobianjie[i]=zuobianjie2[i];

}

if(youbianjie[i]youbianjie2[i])//如果新得到的局部右邊界在上一代局部右邊界右邊，則右邊界取上一代的

{

youbianjie[i]=youbianjie2[i];

}

}

if(chushizhongqunji[0].shiyingduzuiyougeti-shiyingdu)//本代種群的最優(yōu)個體比歷史最有個個體好，則用本代的代替之，并將標(biāo)志位賦值為1表示尋優(yōu)成功

{

for(i=0;ijiedeweishu;i++)

{

zuiyougeti-geti[i]=chushizhongqunji[0].geti[i];

}

zuiyougeti-shiyingdu=chushizhongqunji[0].shiyingdu;

biaozhi=1;

}

delete [] bianjiezancunqi;

delete [] youxiugetiku;

for(i=0;iglpgeshu;i++)

{

delete [] glp_shu_zu[i];

}

delete [] glp_shu_zu;

delete [] chushizhongqunji;

}

void jingyingbaoliu() //精英保留的實現(xiàn)

{

float glpshuliang,xiangliang[jiedeweishu];

if(biaozhi==1)//如果尋優(yōu)成功則利用局部搜索的數(shù)據(jù)

{

glpshuliang=glpgeshu1;

for(int i=0;ijiedeweishu;i++)

{

xiangliang[i]=sheng_cheng_xiang_liang1[i];

}

}

else//否則利用全局搜索的數(shù)據(jù)

{

glpshuliang=glpgeshu2;

for(int i=0;ijiedeweishu;i++)

{

xiangliang[i]=sheng_cheng_xiang_liang2[i];

}

}

chushi *chushizhongqunji;//建立一個用來儲存種群的容器

chushizhongqunji=new chushi[glpshuliang];

int i,j;

float **glp_shu_zu;//生成一個glp數(shù)組

glp_shu_zu=new (float *[glpshuliang]);

for(i=0;iglpshuliang;i++)

{

glp_shu_zu[i]=new float[jiedeweishu];//生成的glp向量用glp_shu_zu儲存

}

glp glp_qiu_jie_first(glpshuliang,jiedeweishu);//定義生成多少組glp向量和向量的維數(shù)

glp_qiu_jie_first.glp_qiu_jie(glp_shu_zu,xiangliang);//將生成的glp向量用glp_shu_zu儲存，同時將生成向量帶入glp類

//cout"377"endl;

if(biaozhi!=1)//如果尋優(yōu)不成功則進(jìn)入全局搜索

{

//cout"380"endl;////////////

float bianjiecha[jiedeweishu];

for(i=0;ijiedeweishu;i++)

{

bianjiecha[i]=youbianjie3[i]-zuobianjie3[i];//計算上一代全局每一維范圍的寬度

}

static float rou=0.9;//定義收縮比

//float rou=pow(0.5,gen);

for(i=0;ijiedeweishu;i++)//確定新的范圍

{

zuobianjie1[i]=zuiyougeti-geti[i]-rou*bianjiecha[i];//左邊界為以最優(yōu)個體為中心-范圍寬度乘以收縮比

if(zuobianjie1[i]zuobianjie2[i])//如果新的左邊界比目前局部左邊界大，那么以目前的為全局尋優(yōu)的左邊界

{

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];//右邊界為以最優(yōu)個體為中心+范圍寬度乘以收縮比

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(chazhi==bianjiecha[0])//如果最大邊界差不變的話就將收縮因子變小

{

rou=pow(rou,2);

}

chazhi=bianjiecha[0];

}

//cout"421"endl;/////////////////////

for(i=0;iglpshuliang;i++)//根據(jù)新產(chǎn)生的最優(yōu)個體確定glp群

{

for(j=0;jjiedeweishu;j++)

{

chushizhongqunji[i].geti[j]=sishewuru((zuobianjie[j]+(youbianjie[j]-(zuobianjie[j]))*glp_shu_zu[i][j]));

}

}

for(i=0;iglpshuliang;i++)

{

mubiaohanshu1(chushizhongqunji[i]);

}

qsort(chushizhongqunji,glpshuliang,sizeof(chushi),cmpshiyingdujiang);

zuiyougetijicunqi-shiyingdu=zuiyougeti-shiyingdu;

if(chushizhongqunji[0].shiyingduzuiyougeti-shiyingdu)

{

for(i=0;ijiedeweishu;i++)

{

zuiyougeti-geti[i]=chushizhongqunji[0].geti[i];

}

zuiyougeti-shiyingdu=chushizhongqunji[0].shiyingdu;

biaozhi=1;

}

else

{

// cout"446"endl;/////////////

biaozhi=0;

}

if(biaozhi==1)//如果尋優(yōu)成功了就需要確立一個新的局部最優(yōu)解范圍

{

chushi *youxiugetiku;

youxiugetiku=new chushi[glpshuliang];

int jishuqi=0;

i=0;

while(chushizhongqunji[i].shiyingduzuiyougetijicunqi-shiyingdu)

{

for(int j=0;jjiedeweishu;j++)

{

youxiugetiku[i].geti[j]=chushizhongqunji[i].geti[j];

}

i++;

}

jishuqi=i;

float *bianjiezancunqi;

bianjiezancunqi=new float[jishuqi];

for(i=0;ijiedeweishu;i++)

{

for(int j=0;jjishuqi;j++)

{

bianjiezancunqi[j]=youxiugetiku[j].geti[i];

}

qsort(bianjiezancunqi,jishuqi,sizeof(float),cmp1);

zuobianjie[i]=bianjiezancunqi[jishuqi-1];

youbianjie[i]=bianjiezancunqi[0];

// coutzuobianjie[i]endl;//////////////

// coutyoubianjie[i]endl;/////////////

// coutendl;///////////////

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;iglpshuliang;i++)

{

delete [] glp_shu_zu[i];

}

delete [] glp_shu_zu;

delete [] chushizhongqunji;

}

void mubiaohanshu1(chushi bianliang)//計算shiyingdu

{

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.shiyingdu=yuanmuchang-sunshi-chanpin;

if(bianliang.shiyingdu!=0)//如果不能正好將木料分成所需尺寸則要多切一刀

{

sunshi=qiegesushi*(bianliang.geti[0]+bianliang.geti[1]+bianliang.geti[2]+bianliang.geti[3]);

}

if(bianliang.shiyingdu0)//罰函數(shù)

{

bianliang.shiyingdu=bianliang.shiyingdu+1e5;

}

bianliang.shiyingdu=-bianliang.shiyingdu;

}

int sishewuru(float x)

{

float y;

int z;

y=x-(int)x;

if(y0.5)

{

z=(int)(x);

}

else

{

z=(int)x;

z=z+1;

}

return z;

}

glp.h源文件貼不下了，把你郵箱給我我發(fā)給你

郵箱：hu_hu605@163.com

找零錢問題 [貪心算法](java實現(xiàn)）

public getMin{

public int MinNumber=0;

public int findMax(int[] a){

for(int i=0;ia.length;i++){

if(a[i]==0) return a[--i];

}

return a[a.length-1];

}

public boolean Compare(int a,int b){

public boolean flag=true;

if(ab) flag=flase;

return flag;

}

public int getMinNumber(int[] M,int Money){

int[] findM=new int[M.length];

int index=0;

for(int i=0;iM.length;i++){

boolean f = this.Compare(M[i],money)

if(f) findM[index++]=M[i];

}

int max = this.findMax(findM);

MinNumber++;

if((Money-max)!=0) {

getMinNumber(M,Money-max)

}

return MinNumber;

}

public int[] Start(){

System.out.println("請輸入查詢組數(shù)");

int group=System.in.read();

int[] M={1,2,5,10,20,50,100};

int[] Result = new Int[group];

int index=0;

while (group-- 0){

System.out.println("請輸入金額");

int money=System.in.read();

Result[index++] = getMinNumber(M,money);

MinNumber=0;

}

}

public void print(int[] MinNumber){

for(int i=0;iMinNumber.length.i++){

System.out.println(MinNumber[i]+" ");

}

}

}

public static void main(String[] args){

new getMin().print(new getMin().Start());

}

沒測試啊，有問題請勿噴，呵呵

JAVA-數(shù)組轉(zhuǎn)化問題

public class test6 {

int a[] = { 1, 2, 3, 4, 5, 6, 7 };

int b[] = { 2, 1, 4, 3, 6, 5, 7 };

public static void main(String args[]) {

test6 test = new test6();

test.go();

}

public void go() {

if (smart(a, b))

System.out.println("n=" + n(a, b));

}

public boolean smart(int[] a, int[] b) {

int a_[] = array(a);

int b_[] = array(b);

if (a.length == b.length) {

for (int c = 0; c a.length; c++) {

if (a_[c] != b_[c]) {

System.out.println("cannot transform");

return false;

}

}

for (int c = 0; c a.length; c++)

System.out.print(a[c]+" ");

System.out.println();

for (int c = 0; c b.length; c++)

System.out.print(b[c]+" ");

System.out.println();

return true;

} else {

System.out.println("cannot transform");

return false;

}

}

public int[] array(int[] a) {

int[] z = new int[a.length];

for (int c = 0; c a.length; c++)

z[c] = a[c];

for (int c = 0; c z.length - 1; c++) {

for (int d = c + 1; d z.length; d++) {

if (z[c] z[d]) {

int x = z[c];

z[c] = z[d];

z[d] = x;

}

}

}

return z;

}

public int n(int[] a, int[] b) {

int c = 0;

for (int d = 0; d a.length; d++)

if (a[d] != b[d])

c += 5;

return (c + 8) / 10;

}

}

java算法設(shè)計問題（貪心算法）

第一、你說的那個東西不叫框架

第二、你用的算法不是多路合并

第三、題目不是讓你合并、是讓你找出最優(yōu)解

解答，我暈這題目有啥解答的啊，你不是自己編的吧，假如合并兩個有序序列只要m+n-1次比較，那么不單單這兩個序列各自有序，同時其中一個序列任意元素大于另外一個序列所有元素

那么答案就是按照k的序號從前想后依次合并啊

java代碼，多機(jī)調(diào)度問題，怎么解釋

多機(jī)調(diào)度問題的Java實現(xiàn)（貪心算法）

具體問題描述以及C/C++實現(xiàn)參見網(wǎng)址

[java]?view?plain?copy?print?

import?java.util.ArrayList;??

import?java.util.Collections;??

import?java.util.LinkedList;??

import?java.util.List;??

/**?

*?多機(jī)調(diào)度問題--貪心算法?

*?@author?Lican?

*?

*/??

public?class?JobMachine?{??

public?static?class?JobNode?implements?Comparable{??

int?id;//作業(yè)的標(biāo)號??

int?time;//作業(yè)時間??

public?JobNode(int?id,int?time){??

this.id=id;??

this.time=time;??

}??

@Override??

public?int?compareTo(Object?x)?{//按時間從大到小排列??

int?times=((JobNode)x).time;??

if(timetimes)?return?-1;??

if(time==times)?return?0;??

return?1;??

}?????????

}??

public?static?class?MachineNode?implements?Comparable{??

int?id;//機(jī)器的標(biāo)號??

int?avail;//機(jī)器空閑的時間（即機(jī)器做完某一項工作的時間）??

public?MachineNode(int?id,int?avail){??

this.id=id;??

this.avail=avail;??

}??

@Override??

public?int?compareTo(Object?o)?{//升序排序，LinkedList的first為最小的??

int?xs=((MachineNode)o).avail;??

if(availxs)?return?-1;??

if(avail==xs)?return?0;??

return?1;??

}??

}??

public?static?int?greedy(int[]?a?,int?m){??

int?n=a.length-1;//a的下標(biāo)從1開始，所以n（作業(yè)的數(shù)目）=a.length-1??

int?sum=0;??

if(n=m){??

for(int?i=0;in;i++)??

sum+=a[i+1];??

System.out.println("為每個作業(yè)分別分配一臺機(jī)器");??

return?sum;??

}??

ListJobNode?d=new?ArrayListJobNode();//d保存所有的作業(yè)??

for(int?i=0;in;i++){//將所有的作業(yè)存入List中，每一項包含標(biāo)號和時間??

JobNode?jb=new?JobNode(i+1,a[i+1]);??

d.add(jb);??

}??

Collections.sort(d);//對作業(yè)的List進(jìn)行排序??

LinkedListMachineNode?h=new?LinkedListMachineNode();//h保存所有的機(jī)器??

for(int?i=1;i=m;i++){//將所有的機(jī)器存入LinkedList中??

MachineNode?x=new?MachineNode(i,0);//初始時，每臺機(jī)器的空閑時間（完成上一個作業(yè)的時間）都為0??

h.add(x);??

}??

int?test=h.size();??

for(int?i=0;in;i++){??

Collections.sort(h);??

MachineNode?x=h.peek();??

System.out.println("將機(jī)器"+x.id+"從"+x.avail+"到"+(x.avail+d.get(i).time)+"的時間段分配給作業(yè)"+d.get(i).id);??

x.avail+=d.get(i).time;??

sum=x.avail;??

}??

return?sum;??

}??

public?static?void?main(String[]?args)?{??

int[]?a={0,2,14,4,16,6,5,3};??

int?m=3;??

int?sum=greedy(a,m);??

System.out.println("總時間為："+sum);??

}??

}??

/**?

運(yùn)行結(jié)果：?

將機(jī)器1從0到16的時間段分配給作業(yè)4?

將機(jī)器2從0到14的時間段分配給作業(yè)2?

將機(jī)器3從0到6的時間段分配給作業(yè)5?

將機(jī)器3從6到11的時間段分配給作業(yè)6?

將機(jī)器3從11到15的時間段分配給作業(yè)3?

將機(jī)器2從14到17的時間段分配給作業(yè)7?

將機(jī)器3從15到17的時間段分配給作業(yè)1?

總時間為：17?

*/

如何用Java語言編程實現(xiàn)下面這道題？

貪心算法: 思路就是對花到第一個噴泉距離從近到遠(yuǎn)排序，然后找到另一個噴泉距離最大的一個

復(fù)雜度O(n^2)。

import java.util.*;

public class Demo {

static long[][] flowers;

public static void main(String[] args) {

Scanner in=new Scanner(System.in);

int n=in.nextInt();

int x1=in.nextInt();

int y1=in.nextInt();

int x2=in.nextInt();

int y2=in.nextInt();

flowers=new long[n][2];

for (int i = 0; i n; i++) {

int x=in.nextInt();

int y=in.nextInt();

flowers[i][0]=dis(x,y,x1,y1);

flowers[i][1]=dis(x,y,x2,y2);

}

Arrays.sort(flowers, (o1, o2) - {

if (o1[0]o2[0])

return -1;

else if (o1[0]==o2[0])

return 0;

else return 1;

});

long temp=0;

long temp2=0;

for (int i = 0; i flowers.length; i++) {

temp=Math.max(temp,flowers[i][1]);

}

for (int i = 0; i flowers.length; i++) {

for (int j = i+1; j flowers.length ; j++) {

if (flowers[j][1]temp2)

temp2=flowers[j][1];

}

temp=Math.min(temp,flowers[i][0]+temp2);

temp2=0;

}

System.out.println(temp);

}

public static long dis(int x,int y,int x1,int y1){

return (long) (x1 - x) *(x1-x)+ (long) (y1 - y) *(y1-y);

}

}

名稱欄目：貪心算法java代碼 貪心算法Java
轉(zhuǎn)載源于：http://jinyejixie.com/article2/hpdcic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營銷推廣、App設(shè)計、微信公眾號、響應(yīng)式網(wǎng)站、ChatGPT、網(wǎng)站內(nèi)鏈

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)