貪心算法java代碼 貪心算法Java
求解一道貪心算法
因為這個問題涉及到高維求解（大于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 shiyingdu;
};
chushi *zuiyougeti;//精英保存策略
chushi *zuiyougetijicunqi;
int sishewuru(float);
float chazhi;//左右邊界的差
int biaozhi;//判斷尋優是否成功1表示成功0表示不成功
int maxgen;//最大計算代數
int gen;//目前代數
void initialize();//算法初始化
void jingyingbaoliu();//精英保存的實現
void mubiaohanshu1(chushi bianliang);//適應度的計算使用殘差法
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);//現在是按降序牌排列，將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);//現在是按降序牌排列，將1和-1互換后就是按升序排列
}
void main()
{
float bianjiebianhuashuzu[jiedeweishu];
float yiwanchengshuliang[jiedeweishu];
zuiyougeti=new chushi;//最優個體的生成
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++)//在這套程序中邊界分為兩個部分,其中一組是根據最優解的收斂范圍進行局部尋優,如果在局部找不到最優解則以現有最優解為中心進行全局搜索
{
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"初始最優解："" "-zuiyougeti-shiyingduendl;/////////////
for(gen=1;genmaxgen;gen++)
{
jingyingbaoliu();
if(chazhi1e-1)
break;
}
//cout"最終在收斂的范圍內左右邊界的最大差值: "chazhiendl;
//for(i=0;ijiedeweishu;i++)
//{
// coutsetiosflags(ios::fixed)setprecision(6)zuiyougeti-geti[i]",";
// }
//coutendl;
//cout"共用代數"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;//最大代數
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向量和向量的維數
glp_qiu_jie_first.glp_qiu_jie(glp_shu_zu,sheng_cheng_xiang_liang);//將生成的glp向量用glp_shu_zu儲存，同時將生成向量帶入glp類
for(i=0;iglpgeshu;i++)//產生初始種群
{
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++)//計算初始種群的適應度
{
mubiaohanshu1(chushizhongqunji[i]);
}
qsort(chushizhongqunji,glpgeshu,sizeof(chushi),cmpshiyingdujiang);//根據適應度將初始種群集按降序進行排列
chushi *youxiugetiku;//建立一個儲存優秀個體的庫
youxiugetiku=new chushi[glpgeshu];//建立一個儲存優秀個體的庫
int jishuqi=0;
i=0;
while(chushizhongqunji[i].shiyingduzuiyougeti-shiyingdu)//凡是比上一代的最優個體還要好的個體都放入優秀個體庫
{
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;//將得到的優秀個體的數量放入jishuqi保存
float *bianjiezancunqi;//下面就要以優秀個體庫中個體的范圍在成立一個局部搜索區域，所以先建立一個邊界暫存器
bianjiezancunqi=new float[jishuqi];
for(i=0;ijiedeweishu;i++)
{
for(int j=0;jjishuqi;j++)
{
bianjiezancunqi[j]=youxiugetiku[j].geti[i];//將優秀個體庫每一維的數據都放入bianjiezancunqi
}
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];
}
}
if(chushizhongqunji[0].shiyingduzuiyougeti-shiyingdu)//本代種群的最優個體比歷史最有個個體好，則用本代的代替之，并將標志位賦值為1表示尋優成功
{
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() //精英保留的實現
{
float glpshuliang,xiangliang[jiedeweishu];
if(biaozhi==1)//如果尋優成功則利用局部搜索的數據
{
glpshuliang=glpgeshu1;
for(int i=0;ijiedeweishu;i++)
{
xiangliang[i]=sheng_cheng_xiang_liang1[i];
}
}
else//否則利用全局搜索的數據
{
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數組
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向量和向量的維數
glp_qiu_jie_first.glp_qiu_jie(glp_shu_zu,xiangliang);//將生成的glp向量用glp_shu_zu儲存，同時將生成向量帶入glp類
//cout"377"endl;
if(biaozhi!=1)//如果尋優不成功則進入全局搜索
{
//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];//左邊界為以最優個體為中心-范圍寬度乘以收縮比
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(chazhi==bianjiecha[0])//如果最大邊界差不變的話就將收縮因子變小
{
rou=pow(rou,2);
}
chazhi=bianjiecha[0];
}
//cout"421"endl;/////////////////////
for(i=0;iglpshuliang;i++)//根據新產生的最優個體確定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)//如果尋優成功了就需要確立一個新的局部最優解范圍
{
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)//罰函數
{
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源文件貼不下了，把你郵箱給我我發給你
郵箱：hu_hu605@163.com
找零錢問題 [貪心算法](java實現）
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("請輸入查詢組數");
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-數組轉化問題
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算法設計問題（貪心算法）
第一、你說的那個東西不叫框架
第二、你用的算法不是多路合并
第三、題目不是讓你合并、是讓你找出最優解
解答，我暈這題目有啥解答的啊，你不是自己編的吧，假如合并兩個有序序列只要m+n-1次比較，那么不單單這兩個序列各自有序，同時其中一個序列任意元素大于另外一個序列所有元素
那么答案就是按照k的序號從前想后依次合并啊
java代碼，多機調度問題，怎么解釋
多機調度問題的Java實現（貪心算法）
具體問題描述以及C/C++實現參見網址
[java]?view?plain?copy?print?
import?java.util.ArrayList;??
import?java.util.Collections;??
import?java.util.LinkedList;??
import?java.util.List;??
/**?
*?多機調度問題--貪心算法?
*?@author?Lican?
*?
*/??
public?class?JobMachine?{??
public?static?class?JobNode?implements?Comparable{??
int?id;//作業的標號??
int?time;//作業時間??
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;//機器的標號??
int?avail;//機器空閑的時間（即機器做完某一項工作的時間）??
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的下標從1開始，所以n（作業的數目）=a.length-1??
int?sum=0;??
if(n=m){??
for(int?i=0;in;i++)??
sum+=a[i+1];??
System.out.println("為每個作業分別分配一臺機器");??
return?sum;??
}??
ListJobNode?d=new?ArrayListJobNode();//d保存所有的作業??
for(int?i=0;in;i++){//將所有的作業存入List中，每一項包含標號和時間??
JobNode?jb=new?JobNode(i+1,a[i+1]);??
d.add(jb);??
}??
Collections.sort(d);//對作業的List進行排序??
LinkedListMachineNode?h=new?LinkedListMachineNode();//h保存所有的機器??
for(int?i=1;i=m;i++){//將所有的機器存入LinkedList中??
MachineNode?x=new?MachineNode(i,0);//初始時，每臺機器的空閑時間（完成上一個作業的時間）都為0??
h.add(x);??
}??
int?test=h.size();??
for(int?i=0;in;i++){??
Collections.sort(h);??
MachineNode?x=h.peek();??
System.out.println("將機器"+x.id+"從"+x.avail+"到"+(x.avail+d.get(i).time)+"的時間段分配給作業"+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);??
}??
}??
/**?
運行結果：?
將機器1從0到16的時間段分配給作業4?
將機器2從0到14的時間段分配給作業2?
將機器3從0到6的時間段分配給作業5?
將機器3從6到11的時間段分配給作業6?
將機器3從11到15的時間段分配給作業3?
將機器2從14到17的時間段分配給作業7?
將機器3從15到17的時間段分配給作業1?
總時間為：17?
*/
如何用Java語言編程實現下面這道題？
貪心算法: 思路就是對花到第一個噴泉距離從近到遠排序，然后找到另一個噴泉距離最大的一個
復雜度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
轉載源于：http://www.yijiale78.com/article2/hpdcic.html
成都網站建設公司_創新互聯，為您提供全網營銷推廣、App設計、微信公眾號、響應式網站、ChatGPT、網站內鏈
聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯
- 微信小程序是用什么語言開發的？ 2014-06-06
- 移動網站接入百度小程序有什么好處? 2016-02-18
- 成都便宜模板小程序開發 2022-07-10
- 揭秘——關于小程序開發的那些常見套路 2022-11-24
- 微信小程序的應用價值在哪里 2015-10-29
- 如何選擇一個正規的小程序開發公司？ 2021-09-24
- 微信小程序的優勢盤點，為什么要做小程序開發 2021-03-05
- 小程序開發好了，企業網站建設還有必要嗎？ 2021-03-07
- 小程序開發過程當中容易出現的幾個錯誤，一定要避免！ 2022-07-13
- 微信小程序開發對哪些行業發展有幫助？ 2020-12-20
- ?微信公眾號開發消息推送功能流程，微信小程序開發消息發送與恢復功能說明 2021-05-20
- 成都小程序開發：新手怎么開發小程序社區？ 2022-07-06