《现代优化计算方法》听课笔记——第一课

2017-11-08

课程概况

任课教师
系统工程研究所：王大志
课程结构
一、绪论
二、禁忌搜索算法
三、遗传算法
四、模拟退火算法
五、粒子群优化算法
六、蚁群优化算法
参考书籍
1.《现代优化计算方法（第二版）》刑文训谢金星编著清华大学出版社（几乎绝版，淘宝价格200左右，所以请各位同学自行解决）
2.《智能优化方法》汪定伟编著高等教育出版社淘宝链接
考评形式
课程出勤：20%
平时练习：20%
项目报告：60%（初步定在18周周五之前上交）

绪论

0-1背包问题（knapsack problem)
Java代码：

package knapsack;
//现有背包容量为200kg
//物品的重量和价值如下：
// 20kg--20
// 25kg--20
// 35kg--50
// 40kg--50
// 50kg--45
// 60kg--45
// 70kg--55
public class GreedyAlgorithm {
	public double[] weight = new double[] {20, 25, 35, 40, 50, 60, 70};//定义重量的数组
	public double[] value = new double[] {20, 20, 50, 50, 45, 45, 55};//定义价值的数组
	public int capacity = 200;//定义背包容量
	public void knapsack1(){
		int size = weight.length; //获取重量数组的长度
		int[] tags = new int[size];//定义顺序数组
		double[] vw = new double[size];//定义性价比数组
		for(int i=0;i<size;i++){
			vw[i] = value[i]/weight[i];//算出性价比
			tags[i] = i;//得到初始的排序
		}
		//冒泡排序，得到性价比从大到小的数组
		for(int i=0;i<size;i++){
			for(int j=i+1;j<size;j++){
				if(vw[i]<vw[j]){
					double change =vw[i];
					vw[i] = vw[j];
					vw[j] = change;
					//得到按照性价比大小的排序
					int tag = tags[i];
					tags[i] = tags[j];
					tags[j] = tag;
				}
			}
		}
		//贪心算法
		for(int i=0;i<size;i++){
			if(capacity>=0){
				System.out.println("添加物品:" + weight[tags[i]]);//以重量作为标注进行输出
				capacity -= weight[tags[i]];
			}
			if(capacity<0){
				capacity+=weight[tags[i]];
				System.out.println("删除物品："+weight[tags[i]]);
			}
		}
		System.out.print(capacity);
	}
	public static void main(String[] args) {
		GreedyAlgorithm gda = new GreedyAlgorithm();
		gda.knapsack1();
	}
}