部分背包的贪婪算法 java_使用JAVA实现算法——贪心算法解决背包问题

packageBasePart;importjava.io.BufferedReader;importjava.io.FileInputStream;importjava.io.IOException;importjava.io.InputStreamReader;/*** 使用贪心算法解决背包问题

* 背包问题：

* 旅行者有背包容量m公斤

* 现在有重量W1,W2,W3,W4....Wn

* 对应的价值V1,V2,V3,V4....Vn

* 运行重复携带，欲求得最大价值

* 贪心算法：求得最好的选择，但是贪心算法不是对于所有的问题都得到整体最优解

* 贪心算法基本思路：

* 1.建立数学模型来描述问题

* 2.把求解问题分成若干个子问题

* 3.对于每一个自问题求得局部最优解

* 4.把子问题的解局部最优解合成原来解问题的一个解

* 贪心算法的实现过程：

* 从一个初始解出发

* while-do朝总目标前进

* 求出可行解的一个解元素

* 由所有解元素组成合成问题的一个可行解*/

public classGreedy {/*解决背包问题

*需要背包容量

*背包价值

*背包剩余容量

*解向量集合*/

private doubletotal_weight;private doubletotal_value;private doublerest_weight;//储存排序数组

privateGood[] arrayValue;privateGood[] arrayWeight;privateGood[] arrayC_P;private intgoodsNum;privateGood[] goods;private doublereal_weight;publicGreedy() {

}public Greedy(int goodsNum,doubletotal_weight) {this.goodsNum=goodsNum;this.total_weight=total_weight;

}public void init(String filename) throwsIOException {/** 1.初始化程序

* 2.从TXT文件中得到商品重量和其价值数组

* 3.初始化序列数组arrayValue/Weight/C_P*/goods=newGood[goodsNum];

BufferedReader data=new BufferedReader(new InputStreamReader(newFileInputStream(filename)));

String buff;

String[] strs;//循环赋值

for(int i=0;i<4;i++){

buff=data.readLine();

strs=buff.split(" ");//根据位次

goods[i]=new Good();//对象数组不仅仅需要初始化数组，对于数组内的每一个对象也需要初始化

goods[i].setName(strs[0]);

goods[i].setValue(Double.parseDouble(strs[1]));

goods[i].setWeight(Double.parseDouble(strs[2]));

goods[i].figureC_P();

}//关闭输入流//成员变量初始化

arrayValue=newGood[goodsNum];

arrayWeight=newGood[goodsNum];

arrayC_P=newGood[goodsNum];//初始化数组

/** 价值由大到小数组*/arrayValue=arrayCopy(goods, arrayValue);//按照价值对arrayValue数组进行重新排列，使用冒泡排序法

for(int i=0;i

for(int j=i+1;j

Good temp=arrayValue[i];

arrayValue[i]=arrayValue[j];

arrayValue[j]=temp;

}

}

}/**质量由小到大数组*/arrayWeight=arrayCopy(goods, arrayWeight);//按照价值对arrayWeight数组进行重新排列，使用冒泡排序法

for(int i=0;i

for(int j=i+1;jarrayWeight[j].getWeight()){

Good temp=arrayWeight[i];

arrayWeight[i]=arrayWeight[j];

arrayWeight[j]=temp;

}

}

}/** 性价比由大到小排列*/arrayC_P=arrayCopy(goods, arrayC_P);//按照价值对arrayC_P数组进行重新排列，使用冒泡排序法

for(int i=0;i

for(int j=i+1;j

Good temp=arrayC_P[i];

arrayC_P[i]=arrayC_P[j];

arrayC_P[j]=temp;

}

}

}

}//用于数组拷贝

publicGood[] arrayCopy(Good[] goods,Good[] arr2){

arr2=goods.clone();returnarr2;

}private voidshow(Good[] goodsarr) {for(Good good:goodsarr){

System.out.println(good.getName()+"\t"+good.getValue()+"\t"+good.getWeight()+"\t"+good.getC_P()+"\t"+good.getNum());

}

}/*三种策略：度量准则

* 依次选取价值最大填充

* 依次选取重量最轻填充

* 依次选取比价最大填充

*

* 方法设计：

* 按照度量准则

* 传递一个按照选择优先级排列的对象数组

* 迭代计算剩余容量

* 返回设计方案*/

public voidstrategy(Good[] goodsArray){

rest_weight=total_weight;for(Good good:goodsArray){int selectNum=(int)Math.floor(rest_weight/good.getWeight());

rest_weight=rest_weight-selectNum*good.getWeight();

good.setNum(selectNum);if(rest_weight

}

}

}public voidcalculate(Good[] goodsArray,String target){

total_value=0;

real_weight=0;//处理结果

System.out.println("在以"+target+"为准则的情况下");for(Good good:goodsArray){

System.out.println(good.getName()+"\t\t数量："+good.getNum());

total_value+=good.getValue()*good.getNum();

real_weight+=good.getWeight()*good.getNum();

}

System.out.println("总价值是:\t"+total_value+"\t总重量是:\t"+real_weight);

}public voidsolve() {/** 业务逻辑

* 将优先级数组*/strategy(arrayValue);

calculate(arrayValue,"价值");

strategy(arrayWeight);

calculate(arrayWeight,"重量");

strategy(arrayC_P);

calculate(arrayC_P,"比值");

}public static void main(String[] args) throwsIOException {

Greedy greedy=new Greedy(4,50);

greedy.init("goods.txt");

greedy.solve();

}

}